International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 02 July 2013

Benny Applebaum, Yoni Moses
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.