## 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 ({µ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.

Author: | Claus Peter SchnorrGND, Horst Helmut Hörner |
---|---|

URN: | urn:nbn:de:hebis:30-12367 |

URL: | http://www.mi.informatik.uni-frankfurt.de/research/papers.html |

Document Type: | Preprint |

Language: | English |

Date of Publication (online): | 2005/07/13 |

Year of first Publication: | 1995 |

Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |

Release Date: | 2005/07/13 |

Note: | Preprint, später in: Advances in Cryptology - Eurocrypt '95 Lecture Notes in Computer Science, Vol. 921, Springer Verlag, 1995, S. 1-12 |

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: | Informatik und Mathematik / Mathematik |

Informatik und Mathematik / Informatik | |

Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |

Licence (German): | Deutsches Urheberrecht |