Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INPUT LOCALITY:
Reports tagged with input locality:
TR11-012 | 2nd February 2011
Andrej Bogdanov, Alon Rosen

#### Input locality and hardness amplification

We establish new hardness amplification results for one-way functions in which each input bit influences only a small number of output bits (a.k.a. input-local functions). Our transformations differ from previous ones in that they approximately preserve input locality and at the same time retain the input size of the original ... more >>>

TR13-098 | 28th June 2013
Benny Applebaum, Yoni Moses

#### Locally Computable UOWHF with Linear Shrinkage

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