TY - CONF T1 - Reducing complexity assumptions for statistically-hiding commitment T2 - In EUROCRYPT Y1 - 2004 A1 - Horvitz,O. A1 - Katz, Jonathan A1 - Koo,C. Y A1 - Morselli,R. AB - Determining the minimal assumptions needed to construct various cryptographic buildingblocks 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. JA - In EUROCRYPT ER -