[Updated on Apr. 18] Integration of CiNii Articles into CiNii Research


Bibliographic Information

Other Title
  • Practical SZK Protocols to Prove Modular Polynomial Relations

Search this article


新たなBit Commitment方式と、それを利用した零知識証明プロトコルの提案を行なう。これを利用することにより、証明者は検証者に委託した秘匿情報が、ある(合同)多項式関係を満たしていることを効率良く証明できる。このプロトコルは統計的零知識証明を持ち、既存方式[Dam93, Dam95, Oka95]より、計算量、通信量共に、1/O(|n|)である(nは合同多項式の法)。ただし、プロトコルの枠組は、IPではなくArgument(Computationally-sound proof)である。すなわち、このプロトコルの健全性は、証明者のカが多項式時間に限定された上で成り立つ。本論文では、多項式時間を超える問題として、変形したRSA問題を仮定する。すなわち、このプロトコルの健全性は変形RSA問題の困難さの基で保証される。一方統計的零知識性は、なんら仮定を必要としない。このプロトコルは、電子現金や同時交換など、複雑な要求条件を持つ各種暗号プロトコルの効率を大幅に高めることが出来る。
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.


  • Technical report of IEICE. ISEC

    Technical report of IEICE. ISEC 97 (182), 53-64, 1997-07-19

    The Institute of Electronics, Information and Communication Engineers

Citations (0)*help

See more


See more

Related Articles

See more

Related Data

See more

Related Books

See more

Related Dissertations

See more

Related Projects

See more

Related Products

See more


  • CRID
  • NII Article ID
  • NII Book ID
  • Text Lang
  • Data Source
    • CiNii Articles

Report a problem

Back to top