Paper 2016/563

Garbling Scheme for Formulas with Constant Size of Garbled Gates

Carmen Kempka, Ryo Kikuchi, Susumu Kiyoshima, and Koutarou Suzuki

Abstract

We provide a garbling scheme which creates garbled circuits of a very small constant size (four bits per gate) for circuits with fan-out one (formulas). For arbitrary fan-out, we additionally need only two ciphertexts per additional connection of each gate output wire. We make use of a trapdoor permutation for which we define a generalized notion of correlation robustness. We show that our notion is implied by PRIV-security, a notion for deterministic (searchable) encryption. We prove our scheme secure in the programmable random oracle model.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in ASIACRYPT 2015
DOI
10.1007/978-3-662-48797-6_31
Keywords
garbled circuitsconstant size of garbled gatescorrelation robustnessPRIV-security
Contact author(s)
suzuki koutarou @ lab ntt co jp
History
2016-06-03: received
Short URL
https://ia.cr/2016/563
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/563,
      author = {Carmen Kempka and Ryo Kikuchi and Susumu Kiyoshima and Koutarou Suzuki},
      title = {Garbling Scheme for Formulas with Constant Size of Garbled Gates},
      howpublished = {Cryptology ePrint Archive, Paper 2016/563},
      year = {2016},
      doi = {10.1007/978-3-662-48797-6_31},
      note = {\url{https://eprint.iacr.org/2016/563}},
      url = {https://eprint.iacr.org/2016/563}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.