TU Darmstadt / ULB / tuprints

Practical Lattice Basis Sampling Reduction

Ludwig, Christoph :
Practical Lattice Basis Sampling Reduction.
[Online-Edition]
TU Darmstadt
[Ph.D. Thesis], (2006)

[img]
Preview
Dissertation - PDF
diss.pdf
Available under Simple publication rights for ULB.

Download (1835Kb) | Preview
Item Type: Ph.D. Thesis
Title: Practical Lattice Basis Sampling Reduction
Language: English
Abstract:

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.

Alternative Abstract:
Alternative AbstractLanguage
Schnorr stellte 2003 eine neue Methode zur Gitterbasisreduktion vor, die Random Sampling Reduction (RSR). Seine Analyse ergab, dass RSR den mit bisherigen Methoden in vorgegebener Zeit erzielbaren Approximationsfaktor auf die vierte Wurzel senken kann. Leider benötigt RSR zwei Annahmen, die im Allgemeinen nicht zutreffen. Wir präsentieren den Simple Sampling Reduction Algorithmus (SSR), der RSR praktikabel macht, und weitere - alternative - Algorithmen zur Abschätzung der Wahrscheinlichkeit, durch Sampling einen besonders kurzen Vektor zu finden. Wir demonstrieren, dass mit SSR die Reduktionsergebnisse verbessert werden können, und schlagen mehrere Verallgemeinerungen von SSR vor, die Basen mit mehr kurzen Vektoren oder kürzere Laufzeiten erzielen. Wir präsentieren auch einen Quantenalgorithmus, der im Vergleich zu SSR eine quadratische Beschleunigung erzielt. Wir beschreiben mehrere kryptographische Anwendungen, bei denen ein Angreifer durch Sampling Reduction ein Vorteil entsteht. Schließlich skizzieren wir noch das Design von LaRed, einem flexiblen und interaktiv nutzbaren C++ Framework zur Gitterbasisreduktion mit zugehöriger Bibliothek, das neben den bekannten Algorithmen LLL und BKZ auch die in der Arbeit vorgeschlagenen Reduktionsalgorithmen zur Verfügung stellt.German
Uncontrolled Keywords: Gitterbasisreduktion; gitterbasierte Kryptographie; GGH; NTRU; knapsackbasierte Kryptographie
Alternative keywords:
Alternative keywordsLanguage
Gitterbasisreduktion; gitterbasierte Kryptographie; GGH; NTRU; knapsackbasierte KryptographieGerman
lattice basis reduction; lattice based cryptography; GGH; NTRU; Knapsack based cryptographyEnglish
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik
Date Deposited: 17 Oct 2008 09:22
Last Modified: 07 Dec 2012 11:51
Official URL: http://elib.tu-darmstadt.de/diss/000640
URN: urn:nbn:de:tuda-tuprints-6409
License: Simple publication rights for ULB
Referees: Buchmann, Prof. Dr. Johannes and Schnorr, Prof. Dr. Claus-Peter
Advisors: Buchmann, Prof. Dr. Johannes
Refereed: 13 December 2005
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/640
Export:

Actions (login required)

View Item View Item