Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with hash functions:
TR03-066 | 2nd September 2003
Daniele Micciancio

Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor

Lattices have received considerable attention as a potential source of computational hardness to be used in cryptography, after a breakthrough result of Ajtai (STOC 1996) connecting the average-case and worst-case complexity of various lattice problems. The purpose of this paper is twofold. On the expository side, we present a rigorous ... more >>>

TR05-142 | 1st December 2005
Vadim Lyubashevsky, Daniele Micciancio

Generalized Compact Knapsacks are Collision Resistant

The generalized knapsack problem is the following: given $m$ random
elements $a_1,\ldots,a_m\in R$ for some ring $R$, and a target $t\in
R$, find elements $z_1,\ldots,z_m\in D$ such that $\sum{a_iz_i}=t$
where $D$ is some given subset of $R$. In (Micciancio, FOCS 2002),
it was proved that for appropriate choices of $R$ ... more >>>

TR15-027 | 25th February 2015
Benny Applebaum

Cryptographic Hardness of Random Local Functions -- Survey

Revisions: 1

Constant parallel-time cryptography allows to perform complex cryptographic tasks at an ultimate level of parallelism, namely, by local functions that each of their output bits depend on a constant number of input bits. A natural way to obtain local cryptographic constructions is to use \emph{random local functions} in which each ... more >>>

TR17-008 | 14th January 2017
Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan

Low-Complexity Cryptographic Hash Functions

Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is {\em collision resistant} hash functions (CRH), which prevent an efficient attacker from finding ... more >>>

TR17-099 | 5th June 2017
Nir Bitansky, Omer Paneth, Yael Tauman Kalai

Multi-Collision Resistance: A Paradigm for Keyless Hash Functions

Revisions: 2

We study multi-collision-resistant hash functions --- a natural relaxation of collision-resistant hashing that only guarantees the intractability of finding many (rather than two) inputs that map to the same image. An appealing feature of such hash functions is that unlike their collision-resistant counterparts, they do not necessarily require a key. ... more >>>

ISSN 1433-8092 | Imprint