Paper 2011/324

On the Efficiency of Bit Commitment Reductions

Samuel Ranellucci, Alain Tapp, Severin Winkler, and Jürg Wullschleger


Two fundamental building blocks of secure two-party computation are oblivious transfer and bit commitment. While there exist unconditionally secure implementations of oblivious transfer from noisy correlations or channels that achieve constant rates, similar constructions are not known for bit commitment. In this paper we show that any protocol that implements $n$ instances of bit commitment with an error of at most $2^{-k}$ needs at least $\Omega(kn)$ instances of a given resource such as oblivious transfer or a noisy channel. This implies in particular that it is impossible to achieve a constant rate. We then show that it is possible to circumvent the above lower bound by restricting the way in which the bit commitments can be opened. In the special case where only a constant number of instances can be opened, our protocol achieves a constant rate, which is optimal. Our protocol implements these restricted bit commitments from string commitments and is universally composable. The protocol provides significant speed-up over individual commitments in situations where restricted commitments are sufficient.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
secure two-party computationbit commitmentstring commitmentoblivious transfernoisy channelinformation theory
Contact author(s)
swinkler @ ethz ch
2011-06-17: received
Short URL
Creative Commons Attribution


      author = {Samuel Ranellucci and Alain Tapp and Severin Winkler and Jürg Wullschleger},
      title = {On the Efficiency of Bit Commitment Reductions},
      howpublished = {Cryptology ePrint Archive, Paper 2011/324},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.