| 講演抄録／キーワード |
| 講演名 |
2006-03-23 15:05
完全秘匿ビットコミットメントスキームのラウンド数改良
○瀬里義治・小柴健史（埼玉大） |
| 抄録 |
（和） |
一般的な計算量仮定に基づく完全秘匿ビットコミットメント方式のラウンド複雑度の上界を改善する。現在のところ最良の方式はNaor,Ostrovsky,Venkatesan,Yungによるもので、そのラウンド複雑度はO(n)である。本稿では、彼らの方式の単純な並列版(並列度log(n))を考え、O(n/log(n))-ラウンドの方式を得た。単純な並列化は解析上の問題を発生させたが、新しい解析技法の導入によりこの困難を克服した。我々が導入した技法は平均的近似相互独立性とでも呼ぶべきものであるが、これは相互独立性の一般化である。また、相互独立性はNaorらの方式の解析で本質的な役割を果たしている。我々が導入した平均的近似相互独立性の技法は、新方式の解析に対して重要な役割を担うが、また同時にNaorらの方式の安全性証明に対する別証明をも与える。 |
| （英） |
We improve the upper bound on the round complexity for perfectly concealing bit commitment schemes based on the general computational assumption. The best known scheme is the one-way permutation based scheme due to Naor, Ostrovsky, Venkatesan and Yung and its round complexity is O(n). We consider a naive parallel version of their scheme of the multiplicity log(n) and obtain an O(n/log(n))-round scheme. Our improvement answers a question, raised by them, whether their O(n)-round scheme is essential with respect to the round complexity. Though such a parallelization raises an analytic difficulty, we introduce a new analysis technique and then overcome the difficulty. Our technique copes with expected almost pairwise independent random variables instead of the pairwise independence, which is a key property in their analysis. While the expected almost pairwise independence plays an important role in our security proof, it also provides alternative security proof for the original scheme. |
| キーワード |
（和） |
ビットコミットメント / 計算論的束縛性 / 一方向性置換 / 完全秘匿性 / ラウンド複雑度 / ゼロ知識アーギュメント / / |
| （英） |
bit commitment / computational binding / one-way permutation / perfect concealing / round complexity / zero-knowledge argument / / |
| 文献情報 |
信学技報, vol. 105, no. 680, COMP2005-68, pp. 39-46, 2006年3月. |
| 資料番号 |
COMP2005-68 |
| 発行日 |
2006-03-16 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
COMP |
| 開催期間 |
2006-03-22 - 2006-03-23 |
| 開催地（和） |
電気通信大学 |
| 開催地（英） |
The University of Electro-Communications |
| テーマ（和） |
|
| テーマ（英） |
|
| 講演論文情報の詳細 |
| 申込み研究会 |
COMP |
| 会議コード |
2006-03-COMP |
| 本文の言語 |
英語（日本語タイトルあり） |
| タイトル（和） |
完全秘匿ビットコミットメントスキームのラウンド数改良 |
| サブタイトル（和） |
|
| タイトル（英） |
Improvement of the Round Complexity of Perfectly Concealing Bit Commitment Schemes |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
ビットコミットメント / bit commitment |
| キーワード(2)（和/英） |
計算論的束縛性 / computational binding |
| キーワード(3)（和/英） |
一方向性置換 / one-way permutation |
| キーワード(4)（和/英） |
完全秘匿性 / perfect concealing |
| キーワード(5)（和/英） |
ラウンド複雑度 / round complexity |
| キーワード(6)（和/英） |
ゼロ知識アーギュメント / zero-knowledge argument |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
瀬里 義治 / Yoshiharu Seri / セリ ヨシハル |
| 第1著者 所属（和/英） |
埼玉大学 (略称： 埼玉大)
Saitama Univeristy (略称： Saitama Univ.) |
| 第2著者 氏名（和/英/ヨミ） |
小柴 健史 / Takeshi Koshiba / コシバ タケシ |
| 第2著者 所属（和/英） |
埼玉大学 (略称： 埼玉大)
Saitama Univeristy (略称： Saitama Univ.) |
| 第3著者 氏名（和/英/ヨミ） |
/ / |
| 第3著者 所属（和/英） |
(略称： )
(略称： ) |
| 第4著者 氏名（和/英/ヨミ） |
/ / |
| 第4著者 所属（和/英） |
(略称： )
(略称： ) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2006-03-23 15:05:00 |
| 発表時間 |
35分 |
| 申込先研究会 |
COMP |
| 資料番号 |
COMP2005-68 |
| 巻番号（vol） |
vol.105 |
| 号番号（no） |
no.680 |
| ページ範囲 |
pp.39-46 |
| ページ数 |
8 |
| 発行日 |
2006-03-16 (COMP) |