Faster secure two-party computation in the single-execution setting

Xiao Wang*, Alex J. Malozemoff, Jonathan Katz

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

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 preprocessing). 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, 22× 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsJean-Sebastien Coron, Jesper Buus Nielsen
PublisherSpringer Verlag
Pages399-424
Number of pages26
ISBN (Print)9783319566160
DOIs
Publication statusPublished - Jan 1 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10212 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Wang, X., Malozemoff, A. J., & Katz, J. (2017). Faster secure two-party computation in the single-execution setting. In J-S. Coron, & J. B. Nielsen (Eds.), Advances in Cryptology – EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 399-424). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10212 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-56617-7_14