Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-093 | 27th July 2006 00:00

Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme



We explicitly show the upper bound on the round complexity for perfectly concealing bit commitment schemes based on the general computational assumption. The best known scheme in the literature 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. In their conference paper (at CRYPTO'92), they claimed that such a round reduction of any logarithmic factor is achievable. We work out the details of their claim. Namely, we give an explicit justification of the folklore that such a parallelization would not lose the security proof. Though the 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.

ISSN 1433-8092 | Imprint