Paper 2003/037
Strengthening Zero-Knowledge Protocols using Signatures
Juan A. Garay, Philip MacKenzie, and Ke Yang
Abstract
Recently there has been an interest in zero-knowledge protocols with stronger properties, such as concurrency, unbounded simulation soundness, non-malleability, and universal composability. In this paper, we show a novel technique to convert a large class of existing honest-verifier zero-knowledge protocols into ones with these stronger properties in the common reference string model. More precisely, our technique utilizes a signature scheme existentially unforgeable against adaptive chosen-message attacks, and transforms any $\Sigma$-protocol (which is honest-verifier zero-knowledge) into an unbounded simulation sound concurrent zero-knowledge protocol. We also introduce $\Omega$-protocols, a variant of $\Sigma$-protocols for which our technique further achieves the properties of non-malleability and/or universal composability. In addition to its conceptual simplicity, a main advantage of this new technique over previous ones is that it avoids the Cook-Levin theorem, which tends to be rather inefficient. Indeed, our technique allows for very efficient instantiation based on the security of some efficient signature schemes and standard number-theoretic assumptions. For instance, one instantiation of our technique yields a universally composable zero-knowledge protocol under the Strong RSA assumption, incurring an overhead of a small constant number of exponentiations, plus the generation of two signatures.
Note: This version contains minor revisions and corrections.
Metadata
- Available format(s)
-
PDF PS
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Extended abstract in Eurocrypt 2003
- Keywords
- zero knowledgedigital signatures
- Contact author(s)
- philmac @ lucent com
- History
- 2003-08-15: last of 2 revisions
- 2003-02-27: received
- See all versions
- Short URL
- https://ia.cr/2003/037
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2003/037,
author = {Juan A. Garay and Philip MacKenzie and Ke Yang},
title = {Strengthening Zero-Knowledge Protocols using Signatures},
howpublished = {Cryptology {ePrint} Archive, Paper 2003/037},
year = {2003},
url = {https://eprint.iacr.org/2003/037}
}