---
OA_place: repository
OA_type: green
_id: '19738'
abstract:
- lang: eng
  text: "Garbling is a fundamental cryptographic primitive, with numerous theoretical
    and practical applications. Since the first construction by Yao (FOCS’82, ’86),
    a line of work has concerned itself with reducing the communication and computational
    complexity of that construction. One of the most efficient garbling schemes presently
    is the ‘Half Gates’ scheme by Zahur, Rosulek, and Evans (Eurocrypt’15). Despite
    its widespread adoption, the provable security of this scheme has been based on
    assumptions whose only instantiations are in idealized models. For example, in
    their original paper, Zahur, Rosulek, and Evans showed that hash functions satisfying
    a notion called circular correlation robustness (CCR) suffice for this task, and
    then proved that CCR secure hash functions can be instantiated in the random permutation
    model.\r\nIn this work, we show how to securely instantiate the Half Gates scheme
    in the standard model. To this end, we first show how this scheme can be securely
    instantiated given a (family of) weak CCR hash function, a notion that we introduce.
    Furthermore, we show how a weak CCR hash function can be used to securely instantiate
    other efficient garbling schemes, namely the ones by Rosulek and Roy (Crypto’21)
    and Heath (Eurocrypt’24). Thus we believe this notion to be of independent interest.\r\nFinally,
    we construct such weak CCR hash functions using indistinguishability obfuscation
    and one-way functions. The security proof of this construction constitutes our
    main technical contribution. While our construction is not practical, it serves
    as a proof of concept supporting the soundness of these garbling schemes, which
    we regard to be particularly important given the recent initiative by NIST to
    standardize garbling, and the optimizations in Half Gates being potentially adopted."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Anasuya
  full_name: Acharya, Anasuya
  last_name: Acharya
- first_name: Karen
  full_name: Azari, Karen
  last_name: Azari
- first_name: Mirza Ahad
  full_name: Baig, Mirza Ahad
  id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
  last_name: Baig
- first_name: Dennis
  full_name: Hofheinz, Dennis
  last_name: Hofheinz
- first_name: Chethan
  full_name: Kamath, Chethan
  last_name: Kamath
citation:
  ama: 'Acharya A, Azari K, Baig MA, Hofheinz D, Kamath C. Securely instantiating
    ‘Half Gates’ garbling in the standard model. In: <i>28th IACR International Conference
    on Practice and Theory of Public-Key Cryptography</i>. Vol 15677. Springer Nature;
    2025:37-75. doi:<a href="https://doi.org/10.1007/978-3-031-91829-2_2">10.1007/978-3-031-91829-2_2</a>'
  apa: 'Acharya, A., Azari, K., Baig, M. A., Hofheinz, D., &#38; Kamath, C. (2025).
    Securely instantiating ‘Half Gates’ garbling in the standard model. In <i>28th
    IACR International Conference on Practice and Theory of Public-Key Cryptography</i>
    (Vol. 15677, pp. 37–75). Roros, Norway: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-91829-2_2">https://doi.org/10.1007/978-3-031-91829-2_2</a>'
  chicago: Acharya, Anasuya, Karen Azari, Mirza Ahad Baig, Dennis Hofheinz, and Chethan
    Kamath. “Securely Instantiating ‘Half Gates’ Garbling in the Standard Model.”
    In <i>28th IACR International Conference on Practice and Theory of Public-Key
    Cryptography</i>, 15677:37–75. Springer Nature, 2025. <a href="https://doi.org/10.1007/978-3-031-91829-2_2">https://doi.org/10.1007/978-3-031-91829-2_2</a>.
  ieee: A. Acharya, K. Azari, M. A. Baig, D. Hofheinz, and C. Kamath, “Securely instantiating
    ‘Half Gates’ garbling in the standard model,” in <i>28th IACR International Conference
    on Practice and Theory of Public-Key Cryptography</i>, Roros, Norway, 2025, vol.
    15677, pp. 37–75.
  ista: 'Acharya A, Azari K, Baig MA, Hofheinz D, Kamath C. 2025. Securely instantiating
    ‘Half Gates’ garbling in the standard model. 28th IACR International Conference
    on Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography,
    LNCS, vol. 15677, 37–75.'
  mla: Acharya, Anasuya, et al. “Securely Instantiating ‘Half Gates’ Garbling in the Standard
    Model.” <i>28th IACR International Conference on Practice and Theory of Public-Key
    Cryptography</i>, vol. 15677, Springer Nature, 2025, pp. 37–75, doi:<a href="https://doi.org/10.1007/978-3-031-91829-2_2">10.1007/978-3-031-91829-2_2</a>.
  short: A. Acharya, K. Azari, M.A. Baig, D. Hofheinz, C. Kamath, in:, 28th IACR International
    Conference on Practice and Theory of Public-Key Cryptography, Springer Nature,
    2025, pp. 37–75.
conference:
  end_date: 2025-05-15
  location: Roros, Norway
  name: 'PKC: Public-Key Cryptography'
  start_date: 2025-05-12
date_created: 2025-05-25T22:17:02Z
date_published: 2025-05-05T00:00:00Z
date_updated: 2025-06-02T07:01:45Z
day: '05'
department:
- _id: KrPi
- _id: GradSch
doi: 10.1007/978-3-031-91829-2_2
intvolume: '     15677'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2025/281
month: '05'
oa: 1
oa_version: Preprint
page: 37-75
publication: 28th IACR International Conference on Practice and Theory of Public-Key
  Cryptography
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783031918285'
  issn:
  - 0302-9743
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Securely instantiating ‘Half Gates’ garbling in the standard model
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15677
year: '2025'
...