Fast Cut-and-Choose Based Protocol for Malicious Adversary - Protocol

In the previous blog we saw the high level description of the fast cut-and-choose protocol. We will now see how the protocol works

Inputs: P₁ has input x ∈ {0,1}^l and P₂ has input y ∈ {0,1}^l

Specified output: Party P₂ receives f(x,y) and part P₁ receives no output. Length of output is m.

1)      Input Key Choice and Circuit Preparation

a)   P₁ picks random values a₁⁰, a₁¹, …, a_l⁰, a_l¹; r₁,…,r_s ∈_R Z_q and b₁⁰, b₁¹, … , b_m⁰, b_m¹ ∈_R {0,1}ⁿ. 

b)   For each garbled circuit j, P₁ sets the keys for its input wires to:

k_i,j ⁰ = H(g^a_i^0*r_j) and k_i,j ¹ = H(g^a_i^1*r_j)

c)   The keys for output wire i are b_i⁰ and b_i¹. This is same for all garbled circuits.

d)   P₁ constructs GC₁, GC₂,… GC_s - s independent copies of circuit C. The output wire keys in all are the same.

2)      Oblivious Transfers:

a)   P₁ chooses random values x₁,…x_s ∈_R {0,1}ⁿ.

b)   P₂ chooses a random subset J ⊂ [s] where every j ∈ J with probability exactly ½. P₂ sends the set J and his input bits as part of the OT. J is the set of circuits P₂ is going to check.

c)   P₂ receives all keys associated with its input wires in all circuits GC_j for j ∈ J. Also receives the keys associated with its input y in all other circuits. Also receives the keys associated with its input y in all other circuits.

d)   P₂ receives x₁,…x_s ∈_R {0,1}ⁿ for every j ∉ J. This acts as proof that P₂ chose to evaluate these circuits. 

3)      Send Circuits and Commitments

a)   P₁ sends P₂ the following

i)     The garbled circuits.

ii)    Seed of the randomness extractor.

iii)   Commitment to the garbled values associated with P₁’s input.

iv)   Output translation tables.

4)      Send Cut-And-Choose Challenge

a)   P₂ sends P₁ the set J along with x_j for every j ∉ J.

b)   If the values received by P₁ are incorrect, output ⊥ and abort.

5)      P₁ Sends Its Garbled Input Values in the Evaluation-Circuits

a)   P₁ sends the keys associated with its inputs in the evaluation circuits.

6)      Circuit Evaluation

a)   P₂ uses P₁’s key from Step 5 and the keys associated with its own input from Step 2c to evaluate all garbled circuits.

b)   If P₂ receives consistent output across all the garbled circuit and next step doesn’t result in an abort, then this will be the output.

c)   Else if P₂ receives two valid outputs on one output wire (i.e. both b_i⁰ and b_i¹), then it uses these in the next step.

d)   Else it will abort in Step 8b.

7)      Run Secure Computation To Detect Cheating

a)   P₁ defines a circuit with the output wire labels b₁⁰, b₁¹, … , b_m⁰, b_m¹ hardcoded. The circuit computes the following function

i)        P₁’s input is the same input x as from before and has no output

ii)      P₂’s input is a pair of values b0, b1.

iii)    If there exists a hardcoded pair of label such that bi0 = b0 and bi1 = b1, then P₂ receives x. Otherwise it receives no output

b)   The above circuit can be evaluated using any existing secure computation protocol that gives 2^-s security.

8)      Check Circuits for Computing f(x,y):

a)   Send all input garbled values in check-circuits: For every check-circuit, the party P₁ sends the randomness used for the commitment in Step 3. Aborts if there is inconsistency.

b)   Correctness of Check Circuits: For every j ∈ J, P₂ uses the commitment it received in Step 3 and the randomness in previous step to compute both pairs of input keys associated with P₁’s input in GCj

c)   Using these, P₂ decrypts the circuit and verifies that it is a garbled version of C. If there exists a circuit for which it fails, then P₂ aborts.

d)   If there is exists an output wire for which P₂ did not receive a valid value in any evaluation circuit in Step 6, then P₂ aborts.

9)      Verify Consistency of P₁’s Input:

a)   For every input wire P₁ proves using zero-knowledge proof of knowledge, the correctness of its input.

b)   If any of the proofs fail, then P₂ aborts.

10)      Output Evaluation:

a)   If P₂ received no inconsistent outputs from the evaluation circuits, then it decodes the outputs using the encoded translation tables and outputs the string received. 

b)   If P₂ received inconsistent output, then let x be the output that P₂ received from second computation. Then P₂ computes f(x,y) and outputs it. 

Reference: Blazing Fast 2PC in the Offline/Online Setting with Security for Malicious Adversaries Yehuda Lindell and Ben Riva