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 ith 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 seedi as input for a PRF, to generate all the randomness associated with the ith garbled circuit. At the same time, instead of sending his input-wire labels in the clear, he now sends them encrypted with some key ki. Then his input to the OT is (ki , seedi).
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 seedi. 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?
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 ki 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) = (gr, hrgb).
Then in our protocol, the sender picks w, sends h=gw to the receiver and sets the labels of the input wires in the ith garbled circuit to be EGCommit(h; 0, ri,0) and (h; 1, ri,1). Next the sender picks at random w0, w1 such that w = w0 + w1 and sends h0 = gw0 and h1 = gw1. Additionally for the ith circuit, he sends output recovery commitments h0gli,0 and h1gli,1, where li,0 and li,1 are chosen at random. Then the output wire labels of the circuit are set as li,0 and li,1 corresponding to 0 and 1 respectively.
In the cut-and-choose stage:
- If the receiver chooses to check the circuit it receives seedi and recovers the output wire labels. It can then verify the output recovery commitments.
- If he chooses to evaluate, he additionally receives w0 + li,0 and w1 + li,1 (from the sender, encrypted under ki). 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 li,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 li,0 and from the sender’s previous message, w0 + li,0. Hence he can recover w0. Similarly from the second circuit he can recover w1. Given w = w0 + w1, 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 w0 or w1 and not both. For more than one output wire, different w0 w1 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.
Arash Afshar, Payman Mohassel, Benny Pinkas, Ben Riva. Non-Interactive Secure Computation Based on Cut-and-Choose. EUROCRYPT 2014