Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme
Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme
复制标题
基于轮有效单向排列的完美隐藏比特承诺方案
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Yoshiharu Seri
中科院分区：
文献类型：
--
作者：
Takeshi Koshiba;Yoshiharu Seri
我们明确地显示了上界的轮复杂度完美隐藏比特承诺计划的基础上的一般计算假设。在文献中最著名的方案是单向置换的计划，由于Naor，Ostrovsky，Venkatesan和Yung，其轮复杂度为O（n）。我们考虑一个天真的并行版本，他们的计划的多重数logn，并获得一个O（n/logn）轮计划。在他们的会议论文中（在1992年），他们声称这样的一个回合减少任何对数因子是可以实现的。我们研究出他们索赔的细节。也就是说，我们给出了一个明确的理由，民间传说，这样的并行化不会失去安全证明。虽然并行化提出了一个分析的困难，我们引入了一个新的分析技术，然后克服困难。我们的技术处理预期的几乎两两独立的随机变量，而不是两两独立，这是他们的分析中的一个关键属性。虽然期望的几乎两两独立性在我们的安全性证明中起着重要的作用，但它也为原方案提供了另一种安全性证明。
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 logn and obtain an O(n/logn)-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.
影响因子：
2.2
作者：
P. Dumais;D. Mayers;L. Salvail
通讯作者：
P. Dumais;D. Mayers;L. Salvail