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 Citations (Scopus)

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
StatePublished - 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

Optimization
Communication
Secure Computation
Preprocessing
Concretes
Heart

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
Katz, Jonathan ; Ranellucci, Samuel ; Rosulek, Mike ; Wang, Xiao. / Optimizing authenticated garbling for faster secure two-party computation. Advances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings. editor / Hovav Shacham ; Alexandra Boldyreva. Springer Verlag, 2018. pp. 365-391 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{f9a782da3ed84ea086efca4ed73f4a80,
title = "Optimizing authenticated garbling for faster secure two-party computation",
abstract = "Wang et al.{\^A} (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.{\^A} (Eurocrypt 2015). We also show how to avoid sending an information-theoretic MAC for each garbled row. These two optimizations give up{\^A} 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.",
author = "Jonathan Katz and Samuel Ranellucci and Mike Rosulek and Xiao Wang",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/978-3-319-96878-0_13",
language = "English (US)",
isbn = "9783319968773",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "365--391",
editor = "Hovav Shacham and Alexandra Boldyreva",
booktitle = "Advances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings",
address = "Germany",

}

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10993 LNCS, Springer Verlag, pp. 365-391, 38th Annual International Cryptology Conference, CRYPTO 2018, Santa Barbara, United States, 8/19/18. https://doi.org/10.1007/978-3-319-96878-0_13

Optimizing authenticated garbling for faster secure two-party computation. / Katz, Jonathan; Ranellucci, Samuel; Rosulek, Mike; Wang, Xiao.

Advances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings. ed. / Hovav Shacham; Alexandra Boldyreva. Springer Verlag, 2018. p. 365-391 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10993 LNCS).

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

TY - GEN

T1 - Optimizing authenticated garbling for faster secure two-party computation

AU - Katz, Jonathan

AU - Ranellucci, Samuel

AU - Rosulek, Mike

AU - Wang, Xiao

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85052391483&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052391483&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-96878-0_13

DO - 10.1007/978-3-319-96878-0_13

M3 - Conference contribution

AN - SCOPUS:85052391483

SN - 9783319968773

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 365

EP - 391

BT - Advances in Cryptology – CRYPTO 2018 - 38th Annual International Cryptology Conference, 2018, Proceedings

A2 - Shacham, Hovav

A2 - Boldyreva, Alexandra

PB - Springer Verlag

ER -

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