| Presentation | 2006-07-21 Asymptotic Lower Bound on Round Complexity of Bounded Concurrent Black-Box Zero-Knowledge Proof Protocols Hirofumi MURATANI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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 [numerical formula]. Considering it together with our previous result on an upper bound ω(logm), we can conclude that the asymptotic order almost logm is optimal. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | concurrent black-box zero-knowledge / bounded concurrency / round complexity |
| Paper # | ISEC2006-43 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2006/7/14(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Asymptotic Lower Bound on Round Complexity of Bounded Concurrent Black-Box Zero-Knowledge Proof Protocols |
| Sub Title (in English) | |
| Keyword(1) | concurrent black-box zero-knowledge |
| Keyword(2) | bounded concurrency |
| Keyword(3) | round complexity |
| 1st Author's Name | Hirofumi MURATANI |
| 1st Author's Affiliation | Corporate Research & Development Center, Toshiba Corporation() |
| Date | 2006-07-21 |
| Paper # | ISEC2006-43 |
| Volume (vol) | vol.106 |
| Number (no) | 176 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |