Thursday, March 7, 2013

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 xA, yA and Bob holds xB, yB, with x=xA xB, y = yAyB. 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  zA, zB  of  z= xy = xAyA ⊕ xA yB ⊕ xB yA ⊕ xB yB. So they locally compute tA=xAyAand tB=xByB, and  then, using OT, they compute the cross products u=xAyB and v=xByA such that xy=tuv. 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 Kx ∈ {0,1}k . Alice inputs x in a OT and she receives the MAC   Mx= Kxx Δ A. Notice that if y is another message and  My=Kyy Δ A its corresponding MAC, then Alice can locally compute MxMy=(Kx Ky)⊕(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 tA=aAbA and  tB=aBbB and aOT to secure compute u=aAbB and v=aBbA (u,v are the cross products in c=ab=aAbA ⊕ aA bB ⊕ aB bA ⊕ aB bB), 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 yj, j=1, ..., h,  in a OT and receives 
Nj=Lj⊕ yjΓB
for j=1, ..., h and Nj, Lj, ΓB∈ {0,1}n, 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 yj.

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 Nij=Lij⊕ yjΓBi , i=1,...,n and j=1,...,h:
       [ N1 |  . . . | Nh ] = [ L1 | . . . |  Lh  ] ⊕ [ y1ΓB1 | . . . | yhΓBh].
  •  Swap the position of the MACs and the keys:     
     [ L1 |  . . . | Lh ] = [ N1 | . . . |  Nh  ] ⊕ [ y1ΓB1 | . . . | yhΓBh].
  •  Flip the values of columns and rows:   
                      [ L1j   . . .  Lnj ]   =   [ N1j  . . .  Nnj  ] ⊕ [ yjB1  . . .  ΓBn) ],  j=1, . . ., h. 
  •  Rename Mij = Lji,  Kij = Nji, xi ΓBi  and ΓAj  = yj, from which we get the n MACs
           i=1, ..., n and Mi, Ki, Γ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.  



No comments:

Post a Comment