Zero-Knowledge Proofs of Knowledge Without Interaction (Extended Abstract)

A zero-knowledge proof system of knowledge is a protocol between two parties called the prover and the verifier. The prover wants to convince the verifier that he “knows” the proof of a given theorem without revealing any additional information. This is different from a zero-knowledge proof system of membership where the prover convinces the verifier only of the veridicity of the statement. Zero-knowledge proofs of knowledge are very useful tools in the design of secure protocols. Though, the concept of a proof of knowledge is a very subtle one and great care is needed to obtain a satisfying formalization. In this paper, we investigate the concept of a zero-knowledge proof of knowledge in the noninteractive model of [5, 61. Here, the prover and the verifier share a short random string and the only communication allowed is from the prover to the verifier. Although this is a simpler model than the interactive one, still formalizing zeroknowledge proofs of knowledge is a delicate task. The main results of the paper are the following e We present formal definitions for the concept of non-interactive zero-knowledge proofs