Paper 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.

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2015
Keywords
non-interactive zero knowledgeFiat-ShamirSigma protocolsconcrete efficiency
Contact author(s)
lindell @ biu ac il
History
2015-09-06: last of 9 revisions
2014-09-11: received
See all versions
Short URL
https://ia.cr/2014/710
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/710,
      author = {Yehuda Lindell},
      title = {An Efficient Transform from Sigma Protocols to NIZK with a CRS and Non-Programmable Random Oracle},
      howpublished = {Cryptology ePrint Archive, Paper 2014/710},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/710}},
      url = {https://eprint.iacr.org/2014/710}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.