Paper 2015/751

Fast Garbling of Circuits Under Standard Assumptions

Shay Gueron, University of Haifa and Intel Haifa, Israel
Yehuda Lindell, Bar-Ilan University, Israel
Ariel Nof, Bar-Ilan University, Israel
Benny Pinkas, Bar-Ilan University, Israel
Abstract

Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything but the result. Over recent years, secure computation has become practical and considerable effort has been made to make it more and more efficient. A highly important tool in the design of two-party protocols is Yao's garbled circuit construction (Yao 1986), and multiple optimizations on this primitive have led to performance improvements of orders of magnitude over the last years. However, many of these improvements come at the price of making very strong assumptions on the underlying cryptographic primitives being used (e.g., that AES is secure for related keys, that it is circular secure, and even that it behaves like a random permutation when keyed with a public fixed key). The justification behind making these strong assumptions has been that otherwise it is not possible to achieve fast garbling and thus fast secure computation. In this paper, we take a step back and examine whether it is really the case that such strong assumptions are needed. We provide new methods for garbling that are secure solely under the assumption that the primitive used (e.g., AES) is a pseudorandom function. Our results show that in many cases, the penalty incurred is not significant, and so a more conservative approach to the assumptions being used can be adopted.

Note: UPDATE (4.2023): We introduce a small update to the garbling scheme, for the rare case where the two input wires for an AND gate are the same.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. ACM CCS 2015
Keywords
two-partysecure computationgarbling
Contact author(s)
shay @ math haifa ac il
lindell @ biu ac il
ariel nof @ biu ac il
benny @ pinkas net
History
2023-04-11: last of 4 revisions
2015-07-30: received
See all versions
Short URL
https://ia.cr/2015/751
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/751,
      author = {Shay Gueron and Yehuda Lindell and Ariel Nof and Benny Pinkas},
      title = {Fast Garbling of Circuits Under Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/751},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/751}},
      url = {https://eprint.iacr.org/2015/751}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.