@inproceedings{SS13,
 author = {Chih-hao Shen and Abhi Shelat},
 title = {Fast Two-Party Secure Computation with Minimal Assumptions},
 booktitle = {ACM CCS 2013},
 year = {2012},
 numpages = {12},
}

PDF

Almost all existing protocols for secure two-party computation require a specific hardness assumption, such as DDH, discrete logarithm, or a random oracle, even after assuming oracle access to the oblivious transfer functionality for their correctness and/or efficiency. We propose and implement a Yao-based protocol that is secure against malicious adversaries and enjoys the following benefits:

• it requires the minimal hardness assumption, i.e., OTs;
• it uses 10 rounds of communication plus OT rounds;
• it has the optimal overhead complexity (for an approach that uses the circuit-level cut-and-choose technique); and
• it is embarrassingly parallelizable in the sense that each circuit can be processed in a pipelined manner, and all circuits can be processed in parallel.

To achieve these properties, we describe novel solutions for the three main obstacles for achieving security against malicious adversaries in a cut-and-choose garbled-circuit protocol. We propose an efficient proof to establish the generator’s output authenticity; we suggest the use of an auxiliary circuit that computes a hash to ensure the generator’s input consistency; and we advance the performance of Pinkas and Lindell’s state-of-the-art approach for handling the selective failure attack.

Not only does our protocol require weaker cryptographic assumptions, but our implementation of this protocol also demonstrates a several factor improvement over the best prior work which relies on specific number-theoretic assumptions. Thus, we show that performance does not require specific algebraic assumptions.