Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > OUTPUT LOCALITY:
Reports tagged with Output Locality:
TR13-098 | 28th June 2013
Benny Applebaum, Yoni Moses

Locally Computable UOWHF with Linear Shrinkage

Revisions: 2

We study the problem of constructing locally computable Universal One-Way Hash Functions (UOWHFs) $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 ... more >>>




ISSN 1433-8092 | Imprint