# Abstract

### Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction

Claus-Peter Schnorr und Horst Helmut Hörner

Fachbereich Mathematik (AG 7.2) / Informatik

Johann Wolfgang Goethe-Universität Frankfurt am Main

PSF 111932

60054 Frankfurt/Main, Germany

We introduce algorithms for lattice basis reduction that are
improvements of the famous L3-algorithm. If a random L3-reduced
lattice basis b_{1},b_{2},...,b_{n} is given
such that the vector of reduced Gram-Schmidt coefficients
({µ_{i,j}} 1<= j< i<= n) is uniformly distributed
in [0,1)^{n(n-1)/2}, then the pruned enumeration finds with
positive probability a shortest lattice vector. We demonstrate the
power of these algorithms by solving random subset sum problems of
arbitrary density with 74 and 82 many weights, by breaking the
Chor-Rivest cryptoscheme in dimensions 103 and 151 and by breaking
Damgard's hash function.

Download the paper:

Click here to return.