Cryptology ePrint Archive: Report 2014/710

An Efficient Transform from Sigma Protocols to NIZK with a CRS and Non-Programmable Random Oracle

Yehuda Lindell

Abstract: In this short paper, we present a Fiat-Shamir type transform that takes any Sigma protocol for a relation $R$ and outputs a non-interactive zero-knowledge proof (not of knowledge) for the associated language $L_R$, in the common reference string model. As in the Fiat-Shamir transform, we use a hash function $H$. However, zero-knowledge is achieved under standard assumptions in the common reference string model (without any random oracle), and soundness is achieved in the \emph{non-programmable} random oracle model. The concrete computational complexity of the transform is only slightly higher than the original Fiat-Shamir transform.

Category / Keywords: cryptographic protocols / non-interactive zero knowledge, Fiat-Shamir, Sigma protocols, concrete efficiency

Original Publication (with minor differences): IACR-TCC-2015

Date: received 10 Sep 2014, last revised 6 Sep 2015

Contact author: lindell at biu ac il

Available format(s): PDF | BibTeX Citation

Note: The original version of this paper had a small error in the definition of the dual-mode commitment scheme in Section 3.1. This was pointed out in report 2015/770 and has been fixed in this version.

Version: 20150906:203011 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]