Cryptology ePrint Archive: Report 2018/043

Efficient Adaptively Secure Zero-knowledge from Garbled Circuits

Chaya Ganesh and Yashvanth Kondi and 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.

Category / Keywords: Zero-knowledge, Garbled Circuits, Adaptive Security

Original Publication (with major differences): IACR-PKC-2018

Date: received 8 Jan 2018, last revised 16 Jan 2018

Contact author: ganesh at cs nyu edu, ykondi@ccs neu edu, arpita@iisc ac in, arpitapatra10@gmail com, iampratiksarkar@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180116:115434 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]