## Locally Computable Universal One-Way Hash Functions
with Linear Shrinkage

by Benny Applebaum and Yoni Moses

#### Oded's comments

Property (2) in the abstract follows from (1) and (3),
by setting to zero the few exceptional input bits
(i.e., those that effect much more than the average number of outputs).
The construction itself proceeds in two stages.
First it is show that the assumption that random local functions
are one-way implies that they are weakly resilient to forming collisions
in the sense that it is hard to find an image that is far from the given
image and collides with it. Then such weakly resilient UOWHFs
are transformed into standard UOWHFs
while preserving the constant locality and the linear shrinkage.

#### The original abstract

We study the problem of constructing locally computable cryptographic hash
functions which compress a long $n$-bit input string to a shorter $m$-bit
output string. We present the first construction that achieves: (1) constant
output locality, i.e., every bit of the output depends only on a constant
number of bits of the input; (2) constant input locality, i.e., every bit of
the input affects only on a constant number of bits of the output; and (3)
linear shrinkage, i.e., $m=(1-\epsilon) n$ for some constant $\epsilon>0$.

Previous constructions gained only sub-linear shrinkage of $m-n=n^{1-\epsilon}$
and failed to achieve constant input locality. Our construction is based on the
one-wayness of ``random'' local functions -- a variant of an assumption made by
Goldreich. As an application, we obtain a digital signature scheme with a
minimal {\it additive} complexity overhead: signing $n$-bit messages with
security parameter $\kappa$ takes only $O(n+\kappa)$ time instead of
$O(n\kappa)$ as in typical constructions. Previously, such signatures
were only known to exist under an {\it exponential} hardness assumption.

See
ECCC TR13-098

Back to
list of Oded's choices.