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_{A}y_{A }⊕ x_{A}y_{B }⊕ x_{B}y_{A }⊕ x_{B}y_{B}. So they locally compute t_{A}=x_{A}y_{A}and t_{B}=x_{B}y_{B}, and then, using OT, they compute the cross products u=x_{A}y_{B}and v=x_{B}y_{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_{A}b_{A}and t_{B}=a_{B}b_{B}and aOT to secure compute u=a_{A}b_{B}and v=a_{B}b_{A}(u,v are the cross products in c=ab=a_{A}b_{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}^{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 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

_{1 }| . . . | N

_{h}] = [ L

_{1 }| . . . | L

_{h}] ⊕ [ y

_{1}Γ

_{B1}| . . . | y

_{h}Γ

_{Bh}].

- Swap the position of the MACs and the keys:
_{ }

[ L

_{1 }| . . . | L_{h}] = [ N_{1 }| . . . | N_{h}] ⊕ [ y_{1}Γ_{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.

_{}

_{}

_{ }

_{ }

_{ }

_{ }

## No comments:

## Post a Comment