完全秘匿ビットコミットメントスキームのラウンド数改良
スポンサーリンク
概要
- 論文の詳細を見る
一般的な計算量仮定に基づく完全秘匿ビットコミットメント方式のラウンド複雑度の上界を改善する。現在のところ最良の方式はNaor, Ostrovsky, Venkatesan, Yungによるもので、そのラウンド複雑度はO(n)である。本稿では、彼らの方式の単純な並列版(並列度Iog n)を考え、O(n/log n)-ラウンドの方式を得た。単純な並列化は解析上の問題を発生させたが、新しい解析技法の導入によりこの困難を克服した。我々が導入した技法は平均的近似相互独立性とでも呼ぶべきものであるが、これは相互独立性の一般化である。また、相互独立性はNaorらの方式の解析で本質的な役割を果たしている。我々が導入した平均的近似相互独立性の技法は、新方式の解析に対して重要な役割を担うが、また同時にNaorらの方式の安全性証明に対する別証明をも与える。
- 社団法人電子情報通信学会の論文
- 2006-03-16