Paper 2018/043

Efficient Adaptively Secure Zero-knowledge from Garbled Circuits

Chaya Ganesh, Yashvanth Kondi, Arpita Patra, and Pratik Sarkar

Abstract

Zero-knowledge (ZK) protocols are undoubtedly among the central primitives in cryptography, lending their power to numerous applications such as secure computation, voting, auctions, and anonymous credentials to name a few. The study of efficient ZK protocols for non-algebraic statements has seen rapid progress in recent times, relying on the techniques from secure computation. The primary contribution of this work lies in constructing efficient UC-secure constant round ZK protocols from garbled circuits that are secure against $adaptive$ corruptions, with communication linear in the size of the statement. We begin by showing that the practically efficient ZK protocol of Jawurek et al. (CCS 2013) is adaptively secure when the underlying oblivious transfer (OT) satisfies a mild adaptive security guarantee. We gain adaptive security with little to no overhead over the static case. A conditional verification technique is then used to obtain a three-round adaptively secure zero-knowledge argument in the non-programmable random oracle model (NPROM). We draw motivation from state-of-the-art non-interactive secure computation protocols and leveraging specifics of ZK functionality show a two-round protocol that achieves static security. It is a proof, while most known efficient ZK protocols and our three round protocol are only arguments.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in PKC 2018
Keywords
Zero-knowledgeGarbled CircuitsAdaptive Security
Contact author(s)
ganesh @ cs nyu edu
ykondi @ ccs neu edu
arpita @ iisc ac in
arpitapatra10 @ gmail com
iampratiksarkar @ gmail com
History
2018-01-16: revised
2018-01-10: received
See all versions
Short URL
https://ia.cr/2018/043
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/043,
      author = {Chaya Ganesh and Yashvanth Kondi and Arpita Patra and Pratik Sarkar},
      title = {Efficient Adaptively Secure Zero-knowledge from Garbled Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2018/043},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/043}},
      url = {https://eprint.iacr.org/2018/043}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.