| 講演抄録／キーワード |
| 講演名 |
2006-07-21 10:45
限定並行ブラックボックス零知識証明のラウンド数下界
○村谷博文（東芝） |
| 抄録 |
（和） |
プレインモデルにおける、自己合成の場合の$m$-限定並行零知識証明プロトコルのラウンド数の下界を導出する。これは、非限定並行の場合のCanetti-Kilian-Petrank-Rosenの結果を$m$-限定並行に拡張したものである。結果として得られたラウンド数下界は$o(\frac{\log m}{\log\log m})$である。我々が先の研究で得た一般合成の場合のラウンド数の上界（プロトコルが存在する十分条件）$\omega(\log m)$と合わせて考えると、漸近的オーダとしてほぼ$\log m$が最適であることが分かる。 |
| （英） |
We derive a lower bound on the round complexity of an $m$-bounded concurrent black-box zero-knowledge interactive proof protocol. This is an extension of the result of the Canetti-Kilian-Petrank-Rosen to the case of $m$-bounded concurrency. The resulting bound is $o(\frac{\log m}{\log\log m})$. Considering it together with our previous result on an upper bound $\omega(\log m)$, we can conclude that the asymptotic order almost $\log m$ is optimal. |
| キーワード |
（和） |
並行ブラックボックス零知識 / 限定並行性 / ラウンド計算量 / / / / / |
| （英） |
concurrent black-box zero-knowledge / bounded concurrency / round complexity / / / / / |
| 文献情報 |
信学技報, vol. 106, no. 176, ISEC2006-43, pp. 19-26, 2006年7月. |
| 資料番号 |
ISEC2006-43 |
| 発行日 |
2006-07-14 (ISEC) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|