IACR News item: 02 July 2013
Benny Applebaum, Yoni Moses
ePrint ReportWe 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.
Additional news items may be found on the IACR news page.