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.