@article {15089,
	title = {Reducing complexity assumptions for statistically-hiding commitment},
	journal = {Advances in Cryptology{\textendash}EUROCRYPT 2005},
	year = {2005},
	month = {2005///},
	pages = {614 - 614},
	abstract = {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 {\textquotedblleft}sufficiently similar{\textquotedblright} 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.
},
	doi = {10.1007/11426639_4},
	author = {Haitner,I. and Horvitz,O. and Katz, Jonathan and Koo,C. Y and Morselli,R. and Shaltiel,R.}
}
