Paper 2013/423

Locally Computable UOWHF with Linear Shrinkage

Benny Applebaum and Yoni Moses


We study the problem of constructing locally computable Universal One-Way Hash Functions (UOWHFs) $\mathcal{H}:\{0,1\}^n \rightarrow \{0,1\}^m$. A construction with constant \emph{output locality}, where every bit of the output depends only on a constant number of bits of the input, was established by [Applebaum, Ishai, and Kushilevitz, SICOMP 2006]. However, this construction suffers from two limitations: (1) It can only achieve a sub-linear shrinkage of $n-m=n^{1\epsilon}$; and (2) It has a super-constant \emph{input locality}, i.e., some inputs influence a large super-constant number of outputs. This leaves open the question of realizing UOWHFs with constant output locality and linear shrinkage of $n-m= \epsilon n$, or UOWHFs with constant input locality and minimal shrinkage of $n-m=1$. We settle both questions simultaneously by providing the first construction of UOWHFs with linear shrinkage, constant input locality, and constant output locality. Our construction is based on the one-wayness of ``random'' local functions -- a variant of an assumption made by Goldreich (ECCC 2000). Using a transformation of [Ishai, Kushilevitz, Ostrovsky and Sahai, STOC 2008], our UOWHFs give rise to a digital signature scheme with a minimal \emph{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 \emph{exponential} hardness assumption. As an additional contribution, we obtain new locally-computable hardness amplification procedures for UOWHFs that preserve linear shrinkage.

Available format(s)
Publication info
Published elsewhere. An extended abstract of this work appears in Eurocrypt 2013
hash functionsNC0input localityoutput locality
Contact author(s)
benny applebaum @ gmail com
2013-07-02: received
Short URL
Creative Commons Attribution


      author = {Benny Applebaum and Yoni Moses},
      title = {Locally Computable UOWHF with Linear Shrinkage},
      howpublished = {Cryptology ePrint Archive, Paper 2013/423},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.