Paper 2013/423
Locally Computable UOWHF with Linear Shrinkage
Benny Applebaum and Yoni Moses
Abstract
We study the problem of constructing locally computable Universal OneWay 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 sublinear shrinkage of $nm=n^{1\epsilon}$; and (2) It has a superconstant \emph{input locality}, i.e., some inputs influence a large superconstant number of outputs. This leaves open the question of realizing UOWHFs with constant output locality and linear shrinkage of $nm= \epsilon n$, or UOWHFs with constant input locality and minimal shrinkage of $nm=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 onewayness 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 locallycomputable hardness amplification procedures for UOWHFs that preserve linear shrinkage.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. An extended abstract of this work appears in Eurocrypt 2013
 Keywords
 hash functionsNC0input localityoutput locality
 Contact author(s)
 benny applebaum @ gmail com
 History
 20130702: received
 Short URL
 https://ia.cr/2013/423
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/423, author = {Benny Applebaum and Yoni Moses}, title = {Locally Computable UOWHF with Linear Shrinkage}, howpublished = {Cryptology ePrint Archive, Paper 2013/423}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/423}}, url = {https://eprint.iacr.org/2013/423} }