TY - JOUR T1 - Reducing complexity assumptions for statistically-hiding commitment JF - Advances in Cryptology–EUROCRYPT 2005 Y1 - 2005 A1 - Haitner,I. A1 - Horvitz,O. A1 - Katz, Jonathan A1 - Koo,C. Y A1 - Morselli,R. A1 - Shaltiel,R. AB - Determining the minimal assumptions needed to construct various cryptographic building blocks has been a focal point of research in theoretical cryptography. Here, we revisit the following question: what are the minimal assumptions needed to construct statistically-hiding commitment schemes? Previously, it was known how to construct such schemes based on one-way permutations. We improve upon this by constructing statistically-hiding commitment schemes based on approximable-preimage-size one-way functions. These are one-way functions for which there is an efficient way to approximate the number of preimages of a given output. A special case (for which we show a somewhat simpler construction) is that of regular one-way functions where all outputs have the same number of preimages.We utilize two different approaches in constructing statistically-hiding commitment schemes. Our first approach proceeds by showing that the scheme of Naor et al. can be implemented using any one-way function having an output distribution which is “sufficiently similar” to uniform. We then construct one-way functions with this property from approximable-preimage-size one-way functions. Our second approach begins by constructing a commitment scheme which is statistically hiding against an honest-but-curious receiver. We then demonstrate a compiler which transforms any such commitment scheme into one which is statistically hiding even against a malicious receiver. This compiler and its analysis may be of independent interest. M3 - 10.1007/11426639_4 ER -