Paper 2010/120
Universal OneWay Hash Functions and Average Case Complexity via Inaccessible Entropy
Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil Vadhan, and Hoeteck Wee
Abstract
This paper revisits the construction of Universally OneWay Hash Functions (UOWHFs) from any oneway function due to Rompel (STOC 1990). We give a simpler construction of UOWHFs which also obtains better efficiency and security. The construction exploits a strong connection to the recently introduced notion of *inaccessible entropy* (Haitner et al. STOC 2009). With this perspective, we observe that a small tweak of any oneway function f is already a weak form of a UOWHF: Consider F(x, i) that outputs the ibit long prefix of f(x). If F were a UOWHF then given a random x and i it would be hard to come up with x' \neq x such that F(x, i) = F(x', i). While this may not be the case, we show (rather easily) that it is hard to sample x' with almost full entropy among all the possible such values of x'. The rest of our construction simply amplifies and exploits this basic property. With this and other recent works we have that the constructions of three fundamental cryptographic primitives (Pseudorandom Generators, Statistically Hiding Commitments and UOWHFs) out of oneway functions are to a large extent unified. In particular, all three constructions rely on and manipulate computational notions of entropy in similar ways. Pseudorandom Generators rely on the wellestablished notion of pseudoentropy, whereas Statistically Hiding Commitments and UOWHFs rely on the newer notion of inaccessible entropy. In an additional result, we use the notion of inaccessible entropy for reproving the seminal result of Impagliazzo and Levin (FOCS 1989): a reduction from "uniform distribution" average case complexity problems to ones with arbitrary (though polynomial samplable one) distributions.
Note: Updated full version of a Eurocrypt 2010 paper.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. MAJOR revision.Eurocrypt 2010
 DOI
 10.1007/9783642131905_31
 Keywords
 foundations
 Contact author(s)
 hoeteck @ alum mit edu
 History
 20141211: revised
 20100305: received
 See all versions
 Short URL
 https://ia.cr/2010/120
 License

CC BY
BibTeX
@misc{cryptoeprint:2010/120, author = {Iftach Haitner and Thomas Holenstein and Omer Reingold and Salil Vadhan and Hoeteck Wee}, title = {Universal OneWay Hash Functions and Average Case Complexity via Inaccessible Entropy}, howpublished = {Cryptology ePrint Archive, Paper 2010/120}, year = {2010}, doi = {10.1007/9783642131905_31}, note = {\url{https://eprint.iacr.org/2010/120}}, url = {https://eprint.iacr.org/2010/120} }