Theory of Computing
-------------------
Title : Inaccessible Entropy II: IE Functions and Universal One-Way Hashing
Authors : Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil Vadhan, and Hoeteck Wee
Volume : 16
Number : 8
Pages : 1-55
URL : http://www.theoryofcomputing.org/articles/v016a008
Abstract
--------
This paper uses a variant of the notion of _inaccessible entropy_
(Haitner, Reingold, Vadhan and Wee, STOC 2009), to give an alternative
construction and proof for the fundamental result, first proved by
Rompel (STOC 1990), that _Universal One-Way Hash Functions (UOWHFs)_
can be based on any one-way functions. We observe that a small tweak
of any one-way function $f$ is already a weak form of a UOWHF:
consider the function $F(x,i)$ that returns the $i$-bit-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. Combined with other recent work, the
construction of three fundamental cryptographic primitives
(Pseudorandom Generators, Statistically Hiding Commitments and UOWHFs)
out of one-way functions is now 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 well-established notion of pseudoentropy,
whereas Statistically Hiding Commitments and UOWHFs rely on the newer
notion of inaccessible entropy.
In an additional result we reprove the seminal result of Impagliazzo
and Levin (FOCS 1989): a reduction from "uniform distribution"
average-case complexity problems to ones with arbitrary (polynomial-
time samplable) distributions. We do that using techniques similar to
those we use to construct UOWHFs from one-way functions, where the
source of this similarity is the use of a notion similar to
inaccessible entropy. This draws an interesting connection between two
seemingly separate lines of research: average-case complexity and
universal one-way hash-functions.
------------
A preliminary version of this paper appeared as "Universal One-Way
Hash Functions via Inaccessible Entropy" in EUROCRYPT 2010.