Oded Goldreich, Shai Halevi

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.

Oded Goldreich, Dana Ron, Madhu Sudan

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 >>>