For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Statistical Zero-Knowledge Protocols to Prove Modular Polynomial Relations
Eiichiro FUJISAKI Tatsuaki OKAMOTO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/01/25
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)>>
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.