On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model

In this paper we study the notion of a

Double-Round

NIZ- KPK in the SRS model. In a Double-Round NIZKPK prover and verifier have access to the same random string Σ and, in addition, the prover is allowed to send one message to the verifier before Σ is made available. The verifier needs not to reply to this message. The random string and initial prover message can then be used in any polynomial number of proofs each consisting of a single message.

We show how to construct Double-Round

non-malleable

NIZKPKs in the SRS model by only requiring the existence of

one-way trapdoor permutations

. In contrast, regular NIZKPKs require the existence of cryptosystems with an extra density property, called dense secure cryptosystems. We then show that Double-Round NIZKPKs can replace one-round NIZKPKs in the design of secure protocols. The replacement has no significant effect on the round complexity of the larger protocol but it removes the need of the existence of dense secure cryptosystems. We give examples of cryptographic constructions that use one-round NIZKPKs and that are improved when using Double-Round NIZKPKs: 1) the construction of 3-round resettable zero-knowledge arguments in the UPK model [EUROCRYPT 2001]; 2) the construction of a constant-round (

n

– 1)-secure simulatable coin-flipping protocol [EUROCRYPT 2003].