@article{oai:sucra.repo.nii.ac.jp:00016116,
 author = {小柴, 健史 and SERI, Yoshiharu},
 journal = {埼玉大学紀要. 工学部 第1編 第1部 論文集, The Science and Engineering Reports of Saitama University},
 month = {},
 note = {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., text, application/pdf},
 pages = {40--47},
 title = {Improvement of the Round Complexity of Perfectly Concealing Bit Commitment Schemes<論文>},
 volume = {39},
 year = {2006},
 yomi = {コシバ, タケシ and セリ, ヨシハル}
}