[Resource Topic] 2003/037: Strengthening Zero-Knowledge Protocols using Signatures

Welcome to the resource topic for 2003/037

Strengthening Zero-Knowledge Protocols using Signatures

Authors: Juan A. Garay, Philip MacKenzie, Ke Yang


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

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

ePrint: https://eprint.iacr.org/2003/037

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .