Foundations of garbled circuits
Top Cited Papers
- 16 October 2012
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 784-796
- https://doi.org/10.1145/2382196.2382279
Abstract
Garbled circuits, a classical idea rooted in the work of Yao, have long been understood as a cryptographic technique, not a cryptographic goal. Here we cull out a primitive corresponding to this technique. We call it a garbling scheme. We provide a provable-security treatment for garbling schemes, endowing them with a versatile syntax and multiple security definitions. The most basic of these, privacy, suffices for two-party secure function evaluation (SFE) and private function evaluation (PFE). Starting from a PRF, we provide an efficient garbling scheme achieving privacy and we analyze its concrete security. We next consider obliviousness and authenticity, properties needed for private and verifiable outsourcing of computation. We extend our scheme to achieve these ends. We provide highly efficient blockcipher-based instantiations of both schemes. Our treatment of garbling schemes presages more efficient garbling, more rigorous analyses, and more modularly designed higher-level protocols.Keywords
This publication has 29 references indexed in Scilit:
- Secure Two-Party Computation Is PracticalLecture Notes in Computer Science, 2009
- Practical Secure Evaluation of Semi-private FunctionsLecture Notes in Computer Science, 2009
- A Proof of Security of Yao’s Protocol for Two-Party ComputationJournal of Cryptology, 2008
- One-Time ProgramsLecture Notes in Computer Science, 2008
- Improved Garbled Circuit: Free XOR Gates and ApplicationsLecture Notes in Computer Science, 2007
- COMPUTATIONALLY PRIVATE RANDOMIZING POLYNOMIALS AND THEIR APPLICATIONScomputational complexity, 2006
- Cryptography in $NC^0$SIAM Journal on Computing, 2006
- Round-Optimal Secure Two-Party ComputationLecture Notes in Computer Science, 2004
- Cryptographic techniques for privacy-preserving data miningACM SIGKDD Explorations Newsletter, 2002
- Secure circuit evaluationJournal of Cryptology, 1990