## CryptoDB

### Paper: Reducing Complexity Assumptions for Statistically-Hiding Commitment

Authors: Omer Horvitz Jonathan Katz Chiu-Yuen Koo Ruggero Morselli URL: http://eprint.iacr.org/2004/341 Search ePrint Search Google 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.
##### BibTeX
@misc{eprint-2004-12305,
title={Reducing Complexity Assumptions for Statistically-Hiding Commitment},
booktitle={IACR Eprint archive},
keywords={foundations /},
url={http://eprint.iacr.org/2004/341},
note={Eurocrypt 2005 jkatz@cs.umd.edu 12860 received 3 Dec 2004, last revised 18 Mar 2005},
author={Omer Horvitz and Jonathan Katz and Chiu-Yuen Koo and Ruggero Morselli},
year=2004
}