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

概要

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