Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Lattice Reduction:
TR96-042 | 26th July 1996
Oded Goldreich, Shai Halevi

Collision-Free Hashing from Lattice Problems

Recently Ajtai described a construction of one-way functions whose
security is equivalent to the difficulty of some well known approximation
problems in lattices. We show that essentially the same
construction can also be used to obtain collision-free hashing.

more >>>

TR98-062 | 28th October 1998
Oded Goldreich, Dana Ron, Madhu Sudan

Chinese Remaindering with Errors

Revisions: 4 , Comments: 1

The Chinese Remainder Theorem states that a positive
integer m is uniquely specified by its remainder modulo
k relatively prime integers p_1,...,p_k, provided
m < \prod_{i=1}^k p_i. Thus the residues of m modulo
relatively prime integers p_1 < p_2 < ... < p_n
form a redundant representation of m if ... more >>>

ISSN 1433-8092 | Imprint