Paper 2022/797

Garbled Circuits With Sublinear Evaluator

Abida Haque, North Carolina State University
David Heath, Georgia Institute of Technology
Vladimir Kolesnikov, Georgia Institute of Technology
Steve Lu, Stealth Software Technologies, Inc.
Rafail Ostrovsky, University of California, Los Angeles
Akash Shah, University of California, Los Angeles, Microsoft Research (India)
Abstract

Arecentlineofwork, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in EUROCRYPT 2022
Keywords
Garbled Circuits Stacked Garbling Private Information Retrieval
Contact author(s)
ahaque3 @ ncsu edu
heath davidanthony @ gatech edu
kolesnikov @ gatech edu
steve @ stealthsoftwareinc com
rafail @ cs ucla edu
akashshah08 @ ucla edu
History
2022-06-20: approved
2022-06-20: received
See all versions
Short URL
https://ia.cr/2022/797
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/797,
      author = {Abida Haque and David Heath and Vladimir Kolesnikov and Steve Lu and Rafail Ostrovsky and Akash Shah},
      title = {Garbled Circuits With Sublinear Evaluator},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/797},
      year = {2022},
      url = {https://eprint.iacr.org/2022/797}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.