1. Faster Secure Two-Party Computation in the Single-Execution Setting 2017 2PC Eurocrypt GarbledCircuits
    Xiao Wang, Alex J. Malozemoff, and Jonathan Katz
    [View PDF on eprint.iacr.org]
    [Show BibTex Citation]

    @misc{cryptoeprint:2016:762,
    author = {Xiao Wang and Alex J. Malozemoff and Jonathan Katz},
    title = {Faster Secure Two-Party Computation in the Single-Execution Setting},
    howpublished = {Cryptology ePrint Archive, Report 2016/762},
    year = {2016},
    note = {\url{https://eprint.iacr.org/2016/762}},
    }

We propose a new protocol for two-party computation, secure against malicious adversaries, that is significantly faster than prior work in the single-execution setting (i.e., non-amortized and with no pre-processing). In particular, for computational security parameter κ and statistical security parameter ρ, our protocol uses only ρ garbled circuits and O(κ) public-key operations, whereas previous work with the same number of garbled circuits required either O(ρn+κ) public-key operations (where n is the input/output length) or a second execution of a secure-computation sub-protocol. Our protocol can be based on the decisional Diffie-Hellman assumption in the standard model.

We implement our protocol to evaluate its performance. With ρ=40, our implementation securely computes an AES evaluation in 65 ms over a local-area network using a single thread without any pre-computation, 22x faster than the best prior work in the non-amortized setting. The relative performance of our protocol is even better for functions with larger input/output lengths.

  1.