TY - GEN
T1 - Garbled Circuits with Sublinear Evaluator
AU - Haque, Abida
AU - Heath, David
AU - Kolesnikov, Vladimir
AU - Lu, Steve
AU - Ostrovsky, Rafail
AU - Shah, Akash
N1 - Funding Information:
Acknowledgements. This work was supported in part by NSF award #1909769, by a Facebook research award, a Cisco research award, and by Georgia Tech’s IISP cyber-security seed funding (CSF) award. This material is also based upon work supported in part by DARPA under Contract No. HR001120C0087. This work is also supported by DARPA under Cooperative Agreement HR0011-20-2-0025, NSF grant CNS-2001096, CNS-1764025, CNS-1718074, US-Israel BSF grant 2015782, Google Faculty Award, JP Morgan Faculty Award, IBM Faculty Research Award, Xerox Faculty Research Award, OKAWA Foundation Research Award, B. John Garrick Foundation Award, Teradata Research Award, Lockheed-Martin Research Award and Sunday Group. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of DARPA, the Department of Defense, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes not withstanding any copyright annotation therein.
Publisher Copyright:
© 2022, International Association for Cryptologic Research.
PY - 2022
Y1 - 2022
N2 - A recent line of work, Stacked Garbled Circuit (SGC), showed that Garbled Circuit (GC) can be improved for functions that include conditional behavior. SGC relieves the communication bottleneck of 2PC by only sending enough garbled material for a single branch out of the b total branches. Hence, communication is sublinear in the circuit size. However, both the evaluator and the generator pay in computation and perform at least factor log b extra work as compared to standard GC. We extend the sublinearity of SGC to also include the work performed by the GC evaluator E; thus we achieve a fully sublinear E, which is essential when optimizing for the online phase. We formalize our approach as a garbling scheme called GCWise: GC WIth Sublinear Evaluator. We show one attractive and immediate application, Garbled PIR, a primitive that marries GC with Private Information Retrieval. Garbled PIR allows the GC to non-interactively and sublinearly access a privately indexed element from a publicly known database, and then use this element in continued GC evaluation.
AB - A recent line of work, Stacked Garbled Circuit (SGC), showed that Garbled Circuit (GC) can be improved for functions that include conditional behavior. SGC relieves the communication bottleneck of 2PC by only sending enough garbled material for a single branch out of the b total branches. Hence, communication is sublinear in the circuit size. However, both the evaluator and the generator pay in computation and perform at least factor log b extra work as compared to standard GC. We extend the sublinearity of SGC to also include the work performed by the GC evaluator E; thus we achieve a fully sublinear E, which is essential when optimizing for the online phase. We formalize our approach as a garbling scheme called GCWise: GC WIth Sublinear Evaluator. We show one attractive and immediate application, Garbled PIR, a primitive that marries GC with Private Information Retrieval. Garbled PIR allows the GC to non-interactively and sublinearly access a privately indexed element from a publicly known database, and then use this element in continued GC evaluation.
UR - http://www.scopus.com/inward/record.url?scp=85131930878&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85131930878&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-06944-4_2
DO - 10.1007/978-3-031-06944-4_2
M3 - Conference contribution
AN - SCOPUS:85131930878
SN - 9783031069437
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 37
EP - 64
BT - Advances in Cryptology – EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022, Proceedings
A2 - Dunkelman, Orr
A2 - Dziembowski, Stefan
PB - Springer
T2 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022
Y2 - 30 May 2022 through 3 June 2022
ER -