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 lattice basis b1,b2,...,bn is given such that the vector of reduced Gram-Schmidt coefficients (
We introduce algorithms for lattice basis reduction that are improvements of the famous L3-algorithm. If a random L3-reduced lattice basis b1,b2,...,bn 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.
show moreshow less

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Claus Peter Schnorr, Horst Helmut Hörner
URN:urn:nbn:de:hebis:30-12367
Document Type:Article
Language:English
Date of Publication (online):2005/07/13
Year of first Publication:1995
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2005/07/13
Source:Advances in Cryptology - Eurocrypt '95 Lecture Notes in Computer Science, Vol. 921, Springer Verlag, pp. 1-12, 1995 , http://www.mi.informatik.uni-frankfurt.de/research/papers.html
HeBIS PPN:22477297X
Institutes:Mathematik
Informatik
Dewey Decimal Classification:510 Mathematik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $