Statistical Zero-Knowledge Protocols to Prove Modular Polynomial Relations

Eiichiro FUJISAKI, Tatsuaki OKAMOTO

Summary :

This paper proposes a bit-commitment scheme, BC(), and an efficient statistical zero-knowledge (in short, SZK) protocol in which, for any given multi-variable polynomial, f(X₁,,X_t), and any given modulus, n, a prover, P, gives (I₁,,I_t) to a verifier,ν, and can convince ν that P knows (x₁,,x_t) which satisfies f(x₁,,x_t) 0 (mod n) and I_i = BC(x_i), (i = 1,,t). The proposed protocol is O(|n|) times more efficient than the corresponding previous ones. The (knowledge) soundness of our protocol holds under a computational assumption, the intractability of a modified RSA problem (see Def. 3.2), while the (statistical) zero-knowledgeness of the protocol needs no computational assumption. The protocol can be employed to construct various practical cryptographic protocols, such as fair exchange, untraceable electronic cash and verifiable secret sharing protocols.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.1 pp.81-92
• Publication Date: 1999/01/25
• Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Authors

Eiichiro FUJISAKI
Tatsuaki OKAMOTO

Keyword

bit commitment,  statistical zero-knowledge,  argument of knowledge