Strengthening Zero-Knowledge Protocols using Signatures

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 new technique that uses a signature scheme that is existentially unforgeable against adaptive chosen message attacks to construct zero-knowledge protocols with these stronger properties in the common reference string model. For instance, using our technique we transform any $Sigma$-protocol (which is honest-verifier zero-knowledge) into an unbounded simulation sound concurrent zero-knowledge protocol. We also introduce 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 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 an unbounded simulation sound zero-knowledge protocol under the Strong RSA assumption, incurring an overhead of a small constant number of exponentiations, plus the generation of two signatures.