Fast two-party secure computation with minimal assumptions

Fast two-party secure computation with minimal assumptions

abhi shelat, Chih-Hao Shen
ACM CCS 2013 [pdf] [bibtex]

This work presents several new techniques and improvements to the cut-and-choose technique for malicious-secure 2PC. Overall, the resulting protocol has complexity ⚠ {$O(kn)$}, where ⚠ {$k$} is the security parameter and ⚠ {$n$} is the size of the target circuit. Furthermore, the protocol relies on general assumptions only: the existence of oblivious-transfer protocols, symmetric encryption, and commitment schemes. We sketch the new techniques below.

In addition, the resulting protocol parallelizes well. It was implemented and evaluated on two high-performance computing clusters.

Output Authenticity

The proposed new approach for output authenticity of the receiver's output is as follows:

  1. Let ⚠ {$v_1, \ldots, v_n$} be wire labels of the same output wire, corresponding to the same truth value, in different garbled circuits. We suppose that the sender has already committed to these values. The receiver must convince the sender that he knows one of the ⚠ {$v_i$} values.
  2. The sender chooses a random value ⚠ {$r$} and sends ⚠ {$c_i= Enc_{v_i}(r)$} for each ⚠ {$i$}.
  3. The receiver uses his known ⚠ {$v_i$} value to decrypt the appropriate ⚠ {$c_i$}, and commits to the result ⚠ {$r'$}
  4. The sender opens all ⚠ {$v_i$} values, and the receiver checks that all ciphertexts ⚠ {$c_i$} encrypt the same value. If not, he aborts. Otherwise, the receiver decommits to ⚠ {$r'$}.
  5. The sender checks whether ⚠ {$r = r'$} and, if so, accepts the value on that output wire of the circuit.

Input Consistency

The proposed new approach for input consistency is as follows: The parties evaluate the circuit ⚠ {$g(x\|r, y) = H(x\|r) \| f(x,y)$}, where ⚠ {$f$} is the target functionality, ⚠ {$r$} is an additional randomly chosen input, and ⚠ {$H$} is a suitable 2-universal hash function.

Intuitively, if ⚠ {$H$} is chosen by the receiver after the sender's inputs are fixed (and this can be easily arranged), then 2-universality ensures that different choices of inputs for the sender will lead to different hash outputs, which the receiver can detect. Conversely, if ⚠ {$r$} is sufficiently long (i.e., ⚠ {$x\|r$} has sufficient entropy), then the leftover hash lemma shows that the output ⚠ {$H(x\|r)$} leaks no information about ⚠ {$x$}.

⚠ {$H$} can be instantiated as multiplication by a randomly chosen binary matrix ⚠ {$M$} of appropriate dimensions. Since the matrix ⚠ {$M$} is public, the circuit for multiplication by ⚠ {$M$} simply consists of XOR gates. Using the free XOR optimization, these gates do not increase the cost of the protocol.

Selective Abort

LP07 suggest to handle the problem of selective failure attacks by having the receiver encode his input as follows. Let ⚠ {$M$} be an appropriate matrix, and evaluate the function ⚠ {$g(x,y) = f(x, M \times y)$}, where ⚠ {$y$} is chosen uniformly conditioned on the receiver's true input being ⚠ {$M \times y$}. This work proposes a new construction of matrices ⚠ {$M$} having the required property (called ⚠ {$k$}-probe resistance), which leads to a significant (50-70%) improvement in the number of inputs to the circuit.

Categories:

CutAndChoose