[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

Abstract

新たな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.

Journal

  • 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

References(17)*help

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

Details

  • CRID
    1573387452154369536
  • NII Article ID
    110003296630
  • NII Book ID
    AN10060811
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top