Non-Interactive Secure Computation based on Cut-and-Choose

Non-interactive Secure Computation (NISC) concerns protocols which have only a single round of interaction. We will discuss a NISC protocol which is based on the cut-and-choose paradigm of Lindell and Pinkas.

To quickly recap, the protocol presented by Lindell and Pinkas for two-party computation involves the construction of 3t Yao’s garbled circuits, of which some are selected for checking correctness of construction and the remaining are used for the computation. Their protocol had a cheating probability of 2^-t. The protocol we are going to discuss requires only t circuits to achieve the same cheating probability.

We begin with a brief overview of three flavours of NISC:

• One-Sender NISC (OS-NISC): It involves two parties, one sender and one receiver. The receiver sends the first message and the sender replies with the second message. The receiver then outputs the result of the computation.
• Multi-Sender NISC (MS-NISC): This is an extension where the first message can be used for running secure computation with many different senders. The receiver broadcasts its first message, and parties who wish to participate in the computation reply. The receiver then outputs the result of the computation with all the senders. This is a limitation of MS-NISC, since it requires the receiver has to aggregate and output all the results together.
• Adaptive MS-NISC: The above limitation is removed and the receiver outputs the result of each computation as soon as the message is received. 

We will discuss how this 2PC protocol modifies the cut-and-choose protocol as follows:

Step 1: Squashing interaction in cut-and-choose. This reduces the protocol to a NISC which achieves 2^-t cheating probability with 3t circuits.

Step 2: Reducing the number of garbled circuits from 3t to t.

Step 1: Squashing Cut-and-Choose 2PC to One Round

We begin with the most straightforward approach to cut-and-choose with 3t garbled circuits. The receiver’s first message corresponds to his OT queries for his input bits. The sender then garbles 3t circuits and replies with a message including (1) The 3t garbled circuits (2) The OT answers for the receiver’s query i.e. input-wire labels for the receiver’s input. Note that the OT protocol used has to be some 2-message OT. (3) Input-wire labels for the sender’s own input.

The receiver can now evaluate the circuits and take the majority result to be the output. However we have to answer the following questions of correctness and security. We have to come up with non-interactive solutions to these issues:

• Were the garbled circuits constructed correctly?

The standard cut-and-choose requires the receiver to pick some fraction of the circuits for verification, and the sender to prove that these circuits were constructed correctly. To simulate this non-interactively, we add 3t OTs called circuit-OTs. In the i^th OT, the receiver queries for 1 if he chooses to check that circuit and 0 if he chooses to evaluate. The sender then inputs messages as follows: He picks a seed seed_i as input for a PRF, to generate all the randomness associated with the i^th garbled circuit. At the same time, instead of sending his input-wire labels in the clear, he now sends them encrypted with some key k_i. Then his input to the OT is (k_i , seed_i).

If the receiver chooses to check the circuit, he receives the seed used to generate all the randomness. If he chooses to evaluate, he receives the key which allows him to decrypt the sender’s input labels and evaluate. The encryption is necessary – if it was not used, the receiver would be able to generate all the input labels for any check circuit, and compare with the received labels from the sender (which are in the clear), and hence leaking the sender’s input.

• Did the sender use the right input-wire labels in the first set of OTs?

To ensure this, we use an OT protocol in which the second message commits the sender to specific inputs. The randomness used to generate these inputs must also be derived from seed_i. In this case, for a check circuit the receiver can compute the required second message of the OT and verify.

• Was the sender’s input consistent in all 3t circuits?

We use a commitment scheme which supports efficient proof that two commitments are commitments to the same value. Then the sender is required to use commitments to 0 and commitments to 1 as the input-wire labels. Again, we require that the randomness used in the commitments is generated using seed_i. In this case the commitments can be generated by the receiver to check the input-wire labels. 

The protocol also includes input commitments, which are a set of commitments of the actual input bits; and commitment equality proofs, which prove that each input value in the evaluated circuit is equal to the value committed in the corresponding input commitments. These proofs are encrypted using k_i in order to hide them from the receiver in the check circuits.

Step 2: Reducing the number of garbled circuits

To reduce the number of garbled circuits in the above protocol, we use only t circuits and instead of checking a fraction of them, we check a random subset. If all evaluated circuits output the same bit, then the probability of cheating is 2^-t since the sender has to guess the exact circuits chosen for checking and evaluation. However if some of the evaluated circuits output different bits, it implies that the sender is malicious. In this case, we want the receiver to be able to recover the sender’s input and compute the output itself.

For simplicity we assume that the circuit the players use has only one output wire and that the sender has only one input bit. Then a high level overview is as follows:

As we discussed before, the sender’s input wire labels are commitments to the actual values. Say we use El Gamal commitment in a group G with generator g where DDH is hard. Then let EGCommit(h; b, r) = (g^r, h^rg^b).

Then in our protocol, the sender picks w, sends h=g^w to the receiver and sets the labels of the input wires in the i^th garbled circuit to be EGCommit(h; 0, r_i,0) and (h; 1, r_i,1). Next the sender picks at random w₀, w₁ such that w = w₀ + w₁ and sends h₀ = g^w0 and h₁ = g^w1. Additionally for the i^th circuit, he sends output recovery commitments h₀g^li,0 and h₁g^li,1, where l_i,0 and l_i,1 are chosen at random. Then the output wire labels of the circuit are set as l_i,0 and l_i,1 corresponding to 0 and 1 respectively.

In the cut-and-choose stage:

•  If the receiver chooses to check the circuit it receives seed_i and recovers the output wire labels. It can then verify the output recovery commitments.
• If he chooses to evaluate, he additionally receives w₀ + l_i,0 and w₁ + l_i,1 (from the sender, encrypted under k_i). The receiver then verifies the consistency of these values with the output recovery commitments by raising g to these values. If they turn out inconsistent, he aborts. Else, he also checks that the earlier commitment of the computed output l_i,b was valid. If so, he marks the circuit as semi-trusted.

At the end of the evaluation, the receiver is left with either the same output from all semi-trusted circuits, or two outputs from at least two semi-trusted circuits.

Case 1: Same output from all – Since with probability 2^-t at least one good evaluated circuit exists (to manipulate, the sender will have to guess the exact evaluation set), this implies that the output is correct.

Case 2: Two circuits with different output – The receiver initiates the cheating recovery process. Say one of the semi-trusted circuits outputs 0 and the other outputs 1. From the first circuit the receiver gets l_i,0 and from the sender’s previous message, w₀ + l_i,0. Hence he can recover w₀. Similarly from the second circuit he can recover w₁. Given w = w₀ + w₁, he can decrypt the input-commitments and recover the sender’s input. Note that if the sender was honest, all the circuits would give the same output and the receiver would only be able to compute w₀ or w₁ and not both. For more than one output wire, different w₀ w₁ are chosen for each, thus the receiver learns one value from each pair.

This completes our description of non-interactive secure computation based on the cut-and-choose paradigm.

REFERENCE

Arash Afshar, Payman Mohassel, Benny Pinkas, Ben Riva. Non-Interactive Secure Computation Based on Cut-and-Choose. EUROCRYPT 2014