Paper 2017/934

Adaptively Indistinguishable Garbled Circuits

Zahra Jafargholi, Alessandra Scafuro, 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. An adaptively secure scheme allows the adversary to specify the input $x$ after seeing the garbled circuit. Applebaum et al. (CRYPTO '13) showed that in any garbling scheme with adaptive simulation-based security, the size of the garbled input must exceed the output size of the circuit. Here we show how to circumvent this lower bound and achieve significantly better efficiency under the minimal assumption that one-way functions exist by relaxing the security notion from simulation-based to indistinguishability-based. We rely on the recent work of Hemenway et al. (CRYPTO '16) which constructed an adaptive simulation-based garbling scheme under one-way functions. The size of the garbled input in their scheme is as large as the output size of the circuit plus a certain pebble complexity of the circuit, where the latter is (e.g.,) bounded by the space complexity of the computation. By building on top of their construction and adapting their proof technique, we show how to remove the output size dependence in their result when considering indistinguishability-based security. As an application of the above result, we get a symmetric-key functional encryption based on one-way functions, with indistinguishability-based security where the adversary can obtain an unbounded number of function secret keys and then adaptively a single challenge ciphertext. The size of the ciphertext only depends on the maximal pebble complexity of each of the functions but not on the number of functions or their circuit size.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in Tcc 2017
Keywords
Garble CircuitsAdaptive SecurityFunctional Encryption
Contact author(s)
zahra @ cs au dk
History
2017-10-30: revised
2017-09-25: received
See all versions
Short URL
https://ia.cr/2017/934
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/934,
      author = {Zahra Jafargholi and Alessandra Scafuro and Daniel Wichs},
      title = {Adaptively Indistinguishable Garbled Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2017/934},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/934}},
      url = {https://eprint.iacr.org/2017/934}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.