委託された秘匿情報間の合同多項式関係を保証する実用的な統計的零知識プロトコル

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