Study Group: A New Approach to Practical Active-Secure Two-Party Computation

This week's study group, given by Nigel, concerned the paper A New Approach to Practical Active-Secure Two-Party Computation (CRYPTO 2012) by J.B. Nielsen et al. In this paper the authors propose a 2-party UC protocol computational secure against a semi-honest adversary in the random oracle model, in which two parties, Alice and Bob, with some private input bits x and y, respectively, jointly compute a boolean function f(x,y). The main motivation for the paper is to give  a PRACTICAL efficient 2-party protocol with the standard requirements of 1) Correctness (the output of the computation is correct) and 2) Privacy (the output is kept secret). To this purpose they use a new approach based on Oblivious Transfer (OT), actually getting  efficiency from a highly inefficient tool. In particular they introduce a new way of extending OTs: from a small number of seed OTs they can derive, in an actively secure way, a large number of committed OT-like primitives.

Their approach is based on the passive-secure 2-party protocol of [GMW87], that extensively uses OT. The input bits x and y are secret shared in such a way that Alice holds x_A, y_A and Bob holds x_B, y_B, with x=x_A⊕ x_B, y = y_A⊕ y_B. Then the boolean circuit computing the function f(x,y) is evaluated gate-by gate.  Suppose the parties want to compute an AND gate: they need to calculate a random sharing  z_A, z_B  of  z= xy = x_Ay_A ⊕ x_A y_B ⊕ x_B y_A ⊕ x_B y_B. So they locally compute t_A=x_Ay_Aand t_B=x_By_B, and  then, using OT, they compute the cross products u=x_Ay_B and v=x_By_A such that xy=t⊕u⊕v. To achieve active security the authors add information theoretic Message Authentication Code (MAC) to all the shares. The first step is the oblivious authentication of bits (aBit): A party (for example Bob) holds a global key Δ _A ∈ {0,1}^k , where k is the security parameter, and, for each of the Alice's bit x, a local key K_x ∈ {0,1}^k . Alice inputs x in a OT and she receives the MAC   M_x= K_x⊕ x Δ _A. Notice that if y is another message and  M_y=K_y⊕ y Δ _A its corresponding MAC, then Alice can locally compute M_x⊕ M_y=(K_x⊕ K_y)⊕(x⊕y) Δ _A. It is important to note that Bob has to  use the same global key  Δ _A for each of the OT. To ensure this  a cut-and-choose-like technique is proposed in which one authenticates twice as many bits as he needs and then he sacrifices  half of them checking that they were done with the same global key. Using aBit, the authors describe  Authenticated AND (aAnd) and Authenticated OT (aOT). If Alice holds authenticated random bits a,b,c, aAnd allows to compute c=ab and  obtain an authentication of this result; aOT permits to perform OT of previously authenticated bits and   produce an authentication on the result.

Summing up  the authors describe a secure 2-party protocol for boolean function in the preprocessing model. During the preprocessing phase  they prepare random authenticated messages, random authenticated multiplication triples and random authenticated OTs, using aBit, aAnd and aOT. In particular aAnd is used to get a MAC on t_A=a_Ab_A and  t_B=a_Bb_B and aOT to secure compute u=a_Ab_B and v=a_Bb_A (u,v are the cross products in c=ab=a_Ab_A ⊕ a_A b_B ⊕ a_B b_A ⊕ a_B b_B), that will be used  in the AND gates during the online phase, where the preprocessed data is used to actually evaluate the circuit. The efficiency  is guaranteed by the OT-extension technique, that from a small number of long MACs on Bob 's random bits permits to derive many, short MACs on Alice's random bits.  Intuitively the OT-extension works as follows:

1) Long MAC for Bob: this first step consists in generating   a few aBit using very long keys. Bob inputs some random bits y_j, j=1, ..., h,  in a OT and receives 

N_j=L_j⊕ y_jΓ_B, 

for j=1, ..., h and N_j, L_j, Γ_B∈ {0,1}ⁿ, with h small (around 128) and n very big. This step is also called LaBit (Leacking Bits) as the key holder (Alice in this case) can learn a few of Bob's bits y_j.

2) Short MAC for Alice. This step consists in generating a lot of aBit with short keys: 

• Rewrite the MACs created in 1) in matrix form N_ij=L_ij⊕ y_jΓ_Bi , i=1,...,n and j=1,...,h:

       [ N₁ |  . . . | N_h ] = [ L₁ | . . . |  L_h  ] ⊕ [ y₁Γ_B1 | . . . | y_hΓ_Bh].

•  Swap the position of the MACs and the keys:     

     [ L₁ |  . . . | L_h ] = [ N₁ | . . . |  N_h  ] ⊕ [ y₁Γ_B1 | . . . | y_hΓ_Bh].

•  Flip the values of columns and rows:   

                      [ L_1j   . . .  L_nj ]   =   [ N_1j  . . .  N_nj  ] ⊕ [ y_j (Γ_B1  . . .  Γ_Bn) ],  j=1, . . ., h. 

•  Rename M_ij = L_ji,  K_ij = N_ji, x_i =  Γ_Bi  and Γ_Aj  = y_j, from which we get the n MACs

 M_i=K_i⊕ x_iΓ_A,

           i=1, ..., n and M_i, K_i, Γ_A∈ {0,1}^k.

This step is called WaBit (Weak Bits) as a few bit of the global key Γ_A may leak to the MAC holder. 

3) Fix the problems obtaining a fully secure global key Δ _A.  

Using these ideas the authors obtain the first practical 2-party computation protocol based on OT at a rate of about 20000 gates for seconds.