| Presentation | 2006-03-23 Improvement of the Round Complexity of Perfectly Concealing Bit Commitment Schemes Yoshiharu SERI, Takeshi KOSHIBA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | bit commitment / computational binding / one-way permutation / perfect concealing / round complexity / zero-knowledge argument |
| Paper # | COMP2005-68 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2006/3/16(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 | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Improvement of the Round Complexity of Perfectly Concealing Bit Commitment Schemes |
| Sub Title (in English) | |
| Keyword(1) | bit commitment |
| Keyword(2) | computational binding |
| Keyword(3) | one-way permutation |
| Keyword(4) | perfect concealing |
| Keyword(5) | round complexity |
| Keyword(6) | zero-knowledge argument |
| 1st Author's Name | Yoshiharu SERI |
| 1st Author's Affiliation | Dept. Information and Computer Sciences, Saitama University() |
| 2nd Author's Name | Takeshi KOSHIBA |
| 2nd Author's Affiliation | Dept. Information and Computer Sciences, Saitama University |
| Date | 2006-03-23 |
| Paper # | COMP2005-68 |
| Volume (vol) | vol.105 |
| Number (no) | 680 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |