Paper 2004/341

Reducing Complexity Assumptions for Statistically-Hiding Commitment

Omer Horvitz, Jonathan Katz, Chiu-Yuen Koo, and Ruggero Morselli


Determining the minimal assumptions needed to construct various cryptographic building blocks has been a focal point of research in theoretical cryptography. For most --- but not all! --- cryptographic primitives, complexity assumptions both necessary and sufficient for their existence are known. Here, we revisit the following, decade-old question: what are the minimal assumptions needed to construct a statistically-hiding bit commitment scheme? Previously, it was known how to construct such schemes based on any one-way permutation. In this work, we show that regular one-way functions suffice. We show two constructions of statistically-hiding commitment schemes from regular one-way functions. Our first construction is more direct, and serves as a ``stepping-stone'' for our second construction which has improved round complexity. Of independent interest, as part of our work we show a compiler transforming any commitment scheme which is statistically-hiding against an honest-but-curious receiver to one which is statistically-hiding against a malicious receiver. This demonstrates the equivalence of these two formulations of the problem. Our results also improve the complexity assumptions needed for statistical zero-knowledge arguments.

Note: This is essentially the version submitted to Eurocrypt 2005. This work is superseded by what will appear in the Eurocrypt 2005 proceedings, but may be of interest as a simpler proof of a weaker result.

Available format(s)
Publication info
Published elsewhere. Eurocrypt 2005
Contact author(s)
jkatz @ cs umd edu
2005-03-18: revised
2004-12-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Omer Horvitz and Jonathan Katz and Chiu-Yuen Koo and Ruggero Morselli},
      title = {Reducing Complexity Assumptions for Statistically-Hiding Commitment},
      howpublished = {Cryptology ePrint Archive, Paper 2004/341},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.