Presentation 1997/7/19
Practical SZK Protocols to Prove Modular Polynomial Relations
Eiichiro FUJISAKI, Tatsuaki OKAMOTO,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) This paper proposes a bit commitment scheme, BC(・), and efficient statistical zero knowledge (in short, SZK) protocols in which, for any given multi-variable polynomial f(X_1, .., X_t) and any given modulus n, prover P gives (I_1, .., I_t) to verifier ν and can convince ν that P knows (x_1, .., x_t) satisfying f(x_1, .., x_t)≡0 (mod n) and I_i=BC(x_i), (i=1, .., t). The proposed protocols are O(lnl) times more efficient than the corresponding previous ones [Dam93, Dam95, Oka95]. The (knowledge) soundness of our protocols hold under a computational assumption, the intractability of a modified RSA problem (see Def.2.3), while the (statistical) zero-knowledgeness of the protocols need no computational assumption. The protocols can be employed to construct various practical cryptographic protocols, such as fair exchange, untraceable electronic cash and verifiable secret sharing protocols.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) bit commitment / witness indistinguishable / statistical zero-knowledge / gradual release protocol / and fair exchange and contract signing / cryptographic protocols
Paper # ISEC97-28
Date of Issue

Conference Information
Committee ISEC
Conference Date 1997/7/19(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Vice Chair

Paper Information
Registration To Information Security (ISEC)
Language ENG
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) Practical SZK Protocols to Prove Modular Polynomial Relations
Sub Title (in English)
Keyword(1) bit commitment
Keyword(2) witness indistinguishable
Keyword(3) statistical zero-knowledge
Keyword(4) gradual release protocol
Keyword(5) and fair exchange and contract signing
Keyword(6) cryptographic protocols
1st Author's Name Eiichiro FUJISAKI
1st Author's Affiliation NTT Laboratories (609A)()
2nd Author's Name Tatsuaki OKAMOTO
2nd Author's Affiliation NTT Laboratories (609A)
Date 1997/7/19
Paper # ISEC97-28
Volume (vol) vol.97
Number (no) 182
Page pp.pp.-
#Pages 12
Date of Issue