Statistical Zero-Knowledge Protocols to Prove Modular Polynomial Relations

Eiichiro FUJISAKI  Tatsuaki OKAMOTO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.1   pp.81-92
Publication Date: 1999/01/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
bit commitment,  statistical zero-knowledge,  argument of knowledge,  

Full Text: PDF(249.3KB)>>
Buy this Article

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(X1,,Xt), and any given modulus, n, a prover, P, gives (I1,,It) to a verifier,ν, and can convince ν that P knows (x1,,xt) which satisfies f(x1,,xt) 0 (mod n) and Ii = BC(xi), (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.