Paper 2019/1210

Adaptive Security of Practical Garbling Schemes

Zahra Jafargholi and Sabine Oechsner

Abstract

A garbling scheme enables one to garble a circuit C and an input x in a way that C(x) can be evaluated, but nothing else is revealed. Since the first construction by Yao, there have been tremendous practical efficiency improvements for selectively secure garbling schemes, where the adversary is forced to choose both input and circuit to be garbled at the same time. However, in the more realistic setting of adaptive security --where an adversary can choose the input adaptively based on the garbled circuit-- not much is known about practical efficiency improvements. In this work, we initiate the study of practical garbling schemes that are both more efficient than Yao's construction and adaptively secure. We provide insights into characteristics of these schemes and highlight the limitations of current techniques for proving adaptive security in this regime. Furthermore, we present an adaptively secure garbling scheme that garbles XOR gates with 2 and AND gates with 3 ciphertexts per gate, thus providing the first practical garbling scheme with adaptive security based on PRFs whose garbled circuit size is smaller than that of Yao's construction.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
garbling schemesadaptive security
Contact author(s)
oechsner @ cs au dk
History
2019-10-16: received
Short URL
https://ia.cr/2019/1210
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1210,
      author = {Zahra Jafargholi and Sabine Oechsner},
      title = {Adaptive Security of Practical Garbling Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1210},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1210}},
      url = {https://eprint.iacr.org/2019/1210}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.