Paper 2016/814

Adaptive Security of Yao's Garbled Circuits

Zahra Jafargholi and Daniel Wichs

Abstract

A garbling scheme is used to garble a circuit $C$ and an input $x$ in a way that reveals the output $C(x)$ but hides everything else. Yao's construction from the 80's is known to achieve selective security, where the adversary chooses the circuit $C$ and the input $x$ in one shot. It has remained as an open problem whether the construction also achieves adaptive security, where the adversary can choose the input $x$ after seeing the garbled version of the circuit $C$. A recent work of Hemenway et al. (CRYPTO '16) modifies Yao's construction and shows that the resulting scheme is adaptively secure. This is done by encrypting the garbled circuit from Yao's construction with a special type of ``somewhere equivocal encryption'' and giving the key together with the garbled input. The efficiency of the scheme and the security loss of the reduction is captured by a certain pebbling game over the circuit. In this work we prove that Yao's construction itself is already adaptively secure, where the security loss can be captured by the same pebbling game. For example, we show that for circuits of depth $d$, the security loss of our reduction is $2^{O(d)}$, meaning that Yao's construction is adaptively secure for NC1 circuits without requiring complexity leveraging. Our technique is inspired by the ``nested hybrids'' of Fuchsbauer et al. (Asiacrypt '14, CRYPTO '15) and relies on a careful sequence of hybrids where each hybrid involves some limited guessing about the adversary's adaptive choices. Although it doesn't match the parameters achieved by Hemenway et al. in their full generality, the main advantage of our work is to prove the security of Yao's construction as is, without any additional encryption layer.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in TCC 2016
Keywords
Garbled CircuitsAdaptive SecuritySecure Computationnested hybrids
Contact author(s)
zahra @ ccs neu edu
History
2016-08-25: received
Short URL
https://ia.cr/2016/814
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/814,
      author = {Zahra Jafargholi and Daniel Wichs},
      title = {Adaptive Security of Yao's Garbled Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2016/814},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/814}},
      url = {https://eprint.iacr.org/2016/814}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.