Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction

We introduce algorithms for lattice basis reduction that are improvements of the famous L3-algorithm. If a random L3-reduced lat- tice basis b₁, ..., 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)^{(_2^n )} $$ , 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 dimen- sions 103 and 151 and by breaking Damgård’s hash function.