Paper 2021/945

Limits on the Adaptive Security of Yao's Garbling

Chethan Kamath, Karen Klein, Krzysztof Pietrzak, and Daniel Wichs


Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting where the adversary chooses the challenge inputs before seeing the garbled circuit assuming secure symmetric-key encryption (and hence one-way functions). This was followed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s scheme (where the output mapping is sent in the online phase, together with the garbled input) that circumvents this negative result, and proved that it is adaptively secure, at least for shallow circuits. In particular, they showed that for the class of circuits of depth $\delta$, the loss in security is at most exponential in $\delta$. The above results all concern the simulation-based notion of security. In this work, we show that the upper bound of Jafargholi and Wichs is basically optimal in a strong sense. As our main result, we show that there exists a family of Boolean circuits, one for each depth $\delta\in\mathbb{N}$, such that any black-box reduction proving the adaptive indistinguishability of the natural adaptation of Yao’s scheme from any symmetric-key encryption has to lose a factor that is exponential in $\sqrt(\delta)$. Since indistinguishability is a weaker notion than simulation, our bound also applies to adaptive simulation. To establish our results, we build on the recent approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction with oracle separations to prove fine-grained lower bounds on loss in cryptographic security.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2021
garbled circuitsadaptive securitylower boundblack-box reduction
Contact author(s)
ckamath @ protonmail com
kklein @ ist ac at
pietrzak @ ist ac at
danwichs @ gmail com
2021-07-13: received
Short URL
Creative Commons Attribution


      author = {Chethan Kamath and Karen Klein and Krzysztof Pietrzak and Daniel Wichs},
      title = {Limits on the Adaptive Security of Yao's Garbling},
      howpublished = {Cryptology ePrint Archive, Paper 2021/945},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.