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*as input for a PRF, to generate all the randomness associated with the i_{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*. In this case, for a check circuit the receiver can compute the required second message of the OT and verify._{i}- Was the sender’s input consistent in all 3t circuits?

*seed*. In this case the commitments can be generated by the receiver to check the input-wire labels.

_{i}
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^{r}g^{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_{0}, w_{1}such that w = w_{0}+ w_{1}and sends h_{0}= g^{w0}and h_{1}= g^{w1}. Additionally for the i^{th}circuit, he sends*output recovery commitments*h_{0}g^{li,0 }and h_{1}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*and recovers the output wire labels. It can then verify the output recovery commitments._{i} - If
he chooses to evaluate, he additionally receives w
_{0}+ l_{i,0}and w_{1}+ 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

_{0}+ l

_{i,0}. Hence he can recover w

_{0}. Similarly from the second circuit he can recover w

_{1}. Given w = w

_{0}+ w

_{1}, 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

_{0}or w

_{1}and not both. For more than one output wire, different w

_{0}w

_{1}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*