Paper 2022/836

Authenticated Garbling from Simple Correlations

Samuel Dittmer, Stealth Software Technologies
Yuval Ishai, Technion
Steve Lu, Stealth Software Technologies
Rafail Ostrovsky, University of California, Los Angeles

We revisit the problem of constant-round malicious secure two-party computation by considering the use of simple correlations, namely sources of correlated randomness that can be securely generated with sublinear communication complexity and good concrete efficiency. The current state-of-the-art protocol of Katz et al. (Crypto 2018) achieves malicious security by realizing a variant of the authenticated garbling functionality of Wang et al. (CCS 2017). Given oblivious transfer correlations, the communication cost of this protocol (with 40 bits of statistical security) is comparable to roughly $10$ garbled circuits (GCs). This protocol inherently requires more than 2 rounds of interaction. In this work, we use other kinds of simple correlations to realize the authenticated garbling functionality with better efficiency. Concretely, we get the following reduced costs in the random oracle model: - Using variants of both vector oblivious linear evaluation (VOLE) and multiplication triples (MT), we reduce the cost to $1.31$ GCs. - Using only variants of VOLE, we reduce the cost to $2.25$ GCs. - Using only variants of MT, we obtain a non-interactive (i.e., 2-message) protocol with cost comparable to $8$ GCs. Finally, we show that by using recent constructions of pseudorandom correlation generators (Boyle et al., CCS 2018, Crypto 2019, 2020), the simple correlations consumed by our protocols can be securely realized without forming an efficiency bottleneck.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Crypto 2022 (To appear)
Two-party computation authenticated garbling garbled circuits NISC
Contact author(s)
samdittmer @ stealthsoftwareinc com
yuval @ cs technion ac il
steve @ stealthsoftwareinc com
rafail @ cs ucla edu
2022-06-27: approved
2022-06-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Samuel Dittmer and Yuval Ishai and Steve Lu and Rafail Ostrovsky},
      title = {Authenticated Garbling from Simple Correlations},
      howpublished = {Cryptology ePrint Archive, Paper 2022/836},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.