Practical Lattice Basis Sampling Reduction.
Technische Universität, Darmstadt
[Ph.D. Thesis], (2006)
Available under Only rights of use according to UrhG.
Download (1MB) | Preview
|Item Type:||Ph.D. Thesis|
|Title:||Practical Lattice Basis Sampling Reduction|
In 2003, Schnorr presented a novel lattice basis reduction method named Random Sampling Reduction (RSR). He concluded that RSR improves the shortest vector approximation factor achievable in fixed time to the fourth root compared with previous methods. Unfortunately, RSR requires two assumptions that we cannot expect to hold in general. We propose Simple Sampling Reduction (SSR) that turns RSR into a practical algorithm and alternative algorithms that estimate the probability of finding a short vector by sampling. We demonstrate that SSR can improve reduction results and propose various generalizations of SSR that yield more short basis vectors or shorter reduction times. We also propose a quantum variant of SSR that yields a quadratic speedup. We show several cryptographic applications where an attacker can gain an advantage by the use of Sampling Reduction. Finally, we outline the design of LaRed, a flexible and interactively usable C++ framework and library for lattice reduction that implements our algorithms besides the well known LLL and BKZ algorithms.
|Place of Publication:||Darmstadt|
|Uncontrolled Keywords:||Gitterbasisreduktion; gitterbasierte Kryptographie; GGH; NTRU; knapsackbasierte Kryptographie|
|Classification DDC:||000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik|
|Divisions:||20 Department of Computer Science|
|Date Deposited:||17 Oct 2008 09:22|
|Last Modified:||07 Dec 2012 11:51|
|Referees:||Buchmann, Prof. Dr. Johannes and Schnorr, Prof. Dr. Claus-Peter|
|Advisors:||Buchmann, Prof. Dr. Johannes|
|Refereed:||13 December 2005|