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

by Benny Applebaum and Yoni Moses

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.