Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Universal One-Way Hash Functions:
TR12-173 | 8th December 2012
Kfir Barhum, Thomas Holenstein

A Cookbook for Black-Box Separations and a Recipe for UOWHFs

We present a new framework for proving fully black-box
separations and lower bounds. We prove a general theorem that facilitates
the proofs of fully black-box lower bounds from a one-way function (OWF).

Loosely speaking, our theorem says that in order to prove that a fully black-box
construction does ... 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