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
Σ-protocol (which is honest-verifier zero-knowledge) into an unbounded simulation sound concurrent zero-knowledge protocol.
We also introduce
Ω-
protocols, a variant of
Σ-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.