---
_id: '10041'
abstract:
- lang: eng
  text: 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   δ , the loss in security is at most exponential in   δ
    . 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  δ∈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   δ√
    . 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.
acknowledgement: We would like to thank the anonymous reviewers of Crypto’21 whose
  detailed comments helped us considerably improve the presentation of the paper.
alternative_title:
- LCNS
article_processing_charge: No
author:
- first_name: Chethan
  full_name: Kamath Hosdurg, Chethan
  id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
  last_name: Kamath Hosdurg
- first_name: Karen
  full_name: Klein, Karen
  id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
  last_name: Klein
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Daniel
  full_name: Wichs, Daniel
  last_name: Wichs
citation:
  ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. Limits on the Adaptive Security
    of Yao’s Garbling. In: <i>41st Annual International Cryptology Conference, Part
    II </i>. Vol 12826. Cham: Springer Nature; 2021:486-515. doi:<a href="https://doi.org/10.1007/978-3-030-84245-1_17">10.1007/978-3-030-84245-1_17</a>'
  apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Wichs, D. (2021). Limits
    on the Adaptive Security of Yao’s Garbling. In <i>41st Annual International Cryptology
    Conference, Part II </i> (Vol. 12826, pp. 486–515). Cham: Springer Nature. <a
    href="https://doi.org/10.1007/978-3-030-84245-1_17">https://doi.org/10.1007/978-3-030-84245-1_17</a>'
  chicago: 'Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Daniel
    Wichs. “Limits on the Adaptive Security of Yao’s Garbling.” In <i>41st Annual
    International Cryptology Conference, Part II </i>, 12826:486–515. Cham: Springer
    Nature, 2021. <a href="https://doi.org/10.1007/978-3-030-84245-1_17">https://doi.org/10.1007/978-3-030-84245-1_17</a>.'
  ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and D. Wichs, “Limits on the
    Adaptive Security of Yao’s Garbling,” in <i>41st Annual International Cryptology
    Conference, Part II </i>, Virtual, 2021, vol. 12826, pp. 486–515.
  ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. 2021. Limits on the Adaptive
    Security of Yao’s Garbling. 41st Annual International Cryptology Conference, Part
    II . CRYPTO: Annual International Cryptology Conference, LCNS, vol. 12826, 486–515.'
  mla: Kamath Hosdurg, Chethan, et al. “Limits on the Adaptive Security of Yao’s Garbling.”
    <i>41st Annual International Cryptology Conference, Part II </i>, vol. 12826,
    Springer Nature, 2021, pp. 486–515, doi:<a href="https://doi.org/10.1007/978-3-030-84245-1_17">10.1007/978-3-030-84245-1_17</a>.
  short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, D. Wichs, in:, 41st Annual International
    Cryptology Conference, Part II , Springer Nature, Cham, 2021, pp. 486–515.
conference:
  end_date: 2021-08-20
  location: Virtual
  name: 'CRYPTO: Annual International Cryptology Conference'
  start_date: 2021-08-16
date_created: 2021-09-23T14:06:15Z
date_published: 2021-08-11T00:00:00Z
date_updated: 2023-09-07T13:32:11Z
day: '11'
department:
- _id: KrPi
doi: 10.1007/978-3-030-84245-1_17
ec_funded: 1
intvolume: '     12826'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2021/945
month: '08'
oa: 1
oa_version: Preprint
page: 486-515
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication: '41st Annual International Cryptology Conference, Part II '
publication_identifier:
  eisbn:
  - 978-3-030-84245-1
  eissn:
  - 1611-3349
  isbn:
  - 978-3-030-84244-4
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '10035'
    relation: dissertation_contains
    status: public
status: public
title: Limits on the Adaptive Security of Yao’s Garbling
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 12826
year: '2021'
...