Optimizing authenticated garbling for faster secure two-party computation

Jonathan Katz, Samuel Ranellucci, Mike Rosulek, Xiao Wang*

*Corresponding author for this work

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

6 Scopus citations

Abstract

Wang et al. (CCS 2017) recently proposed a protocol for malicious secure two-party computation that represents the state-of-the-art with regard to concrete efficiency in both the single-execution and amortized settings, with or without preprocessing. We show here several optimizations of their protocol that result in a significant improvement in the overall communication and running time. Specifically: We show how to make the “authenticated garbling” at the heart of their protocol compatible with the half-gate optimization of Zahur et al. (Eurocrypt 2015). We also show how to avoid sending an information-theoretic MAC for each garbled row. These two optimizations give up to a 2.6 × improvement in communication, and make the communication of the online phase essentially equivalent to that of state-of-the-art semi-honest secure computation.We show various optimizations to their protocol for generating AND triples that, overall, result in a 1.5 × improvement in the communication and a 2 × improvement in the computation for that step.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings
EditorsHovav Shacham, Alexandra Boldyreva
PublisherSpringer Verlag
Pages365-391
Number of pages27
ISBN (Print)9783319968773
DOIs
Publication statusPublished - Jan 1 2018
Event38th Annual International Cryptology Conference, CRYPTO 2018 - Santa Barbara, United States
Duration: Aug 19 2018Aug 23 2018

Publication series

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

Conference

Conference38th Annual International Cryptology Conference, CRYPTO 2018
CountryUnited States
CitySanta Barbara
Period8/19/188/23/18

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Katz, J., Ranellucci, S., Rosulek, M., & Wang, X. (2018). Optimizing authenticated garbling for faster secure two-party computation. In H. Shacham, & A. Boldyreva (Eds.), Advances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings (pp. 365-391). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10993 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-96878-0_13