Welcome to the resource topic for 2013/423
Title:
Locally Computable UOWHF with Linear Shrinkage
Authors: Benny Applebaum, Yoni Moses
Abstract: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.
ePrint: https://eprint.iacr.org/2013/423
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .