TU Darmstadt / ULB / TUprints

Towards Efficient Lattice-Based Cryptography

Lindner, Richard (2011)
Towards Efficient Lattice-Based Cryptography.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PDF (Towards Efficient Lattice-Based Cryptography)
diss-final.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (953kB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Towards Efficient Lattice-Based Cryptography
Language: English
Referees: Buchmann, Prof. Dr. Johannes ; Peikert, Prof. Dr. Christopher
Date: 10 January 2011
Place of Publication: Darmstadt
Date of oral examination: 20 December 2010
Abstract:

One essential quest in cryptography is the search for hard instances of a given computational problem that is known to be hard in the worst-case. In lattice cryptography we are in the unique situation that we have found a way of picking random instances which are at least as hard as well-studied lattice problems in the worst-case. At the same time, no attack running in subexponential time is known to break these problems, even for an adversary using quantum computers. Virtually all public-key schemes in use today are subject to such attacks, and the development of quantum computers is actively pursued, so it is prudent to investigate lattice-based alternatives. There are two fundamental open problems in lattice cryptography today and this thesis contributes to solving them. First, there exists a widely used efficiency improvement that allows for trapdoors whose asymptotic keysize and evaluation time are both quasilinear in the dimension of an associated lattice. This is accomplished by restricting oneself to lattices with special structure, so-called ideal lattices. This entails the use of newer security assumptions, but these have not been analyzed thoroughly so far. We start this work by comparing the class of ideal lattice problems with its general counterpart in terms of size. Affirming folklore, we find the number of restricted instances among all instances to be asymptotically negligible for those classes of lattices suggested for practical use. The second open problem is that while the connection to worst-case problems is well understood, the practical hardness of the related average-case problems is not. Specifically, there have been parameters suggested for practical usage, where current lattice basis reduction algorithms can solve these worst-case problems, but the related average-case problems, which these are reduced to and which represent the basis of practical security of the cryptosystems, are completely infeasible. In most cases, this lack of understanding has lead either to a very conservative choice of parameters, or none at all. This in turn makes it impossible for the resulting lattice schemes to compete with their counterparts based on other paradigms. We further the understanding of this practical security and at the same time improve the efficiency of several common related cryptographic schemes. Among other things, we find that for the SWIFFT compression function, solving certain problems closely related to finding collisions is easier than previously thought and we suggest efficient replacement parameters. We propose a novel zero-knowledge identification scheme that, to our knowledge, beats all competing post-quantum schemes, even those based on other paradigms. Possibly most important, we help to tighten the efficiency gap between lattice encryption schemes that are provably secure and the acclaimed ad-hoc encryption scheme NTRU. This is done by unifying many recent developments into a new provably secure design and providing a comprehensive analysis of practical security, which together results in a great leap of efficiency.

Alternative Abstract:
Alternative AbstractLanguage

In der Kryptographie ist eine der wesentlichen Aufgaben die Suche nach schweren Instanzen eines Berechnungsproblems, von dem man weiß, dass es im Worst-Case schwer ist. In der Gitterkryptographie sind wir in der einzigartigen Situation, einen Weg gefunden zu haben wie man zufällige Instanzen auswählt, die mindestens genauso schwer wie wohluntersuchte Gitterprobleme im Worst-Case sind. Gleichzeitig ist kein Angriff bekannt, der diese Probleme in subexponentieller Zeit löst, selbst wenn der Angreifer einen Quantencomputer verwendet. Praktisch alle asymmetrischen Kryptographieverfahren, die heute im Einsatz sind, unterliegen solchen Angriffen, und die Entwicklung von Quantencomputern, mit denen man die Angriffe praktisch realisieren kann, wird aktiv verfolgt. Es ist daher langfristig gesehen ratsam, gitterbasierte Alternativen zu untersuchen. Es gibt aktuell zwei grundlegende offene Probleme in der Gitterkryptographie, und diese Arbeit trägt zu ihrer Lösung bei. Das erste Problem betrifft eine weit verbreitete Effizienzsteigerung. Diese ermöglicht die Konstruktion von Trapdoor-Einwegfunktionen, deren asymptotische Schlüssellänge und Laufzeit beide quasilinear in der Dimension eines assoziierten Gitters sind. Dies wird durch die Einschränkung des Verfahrens auf Gitter mit spezieller Struktur erreicht, so genannte Idealgitter. Dies ist jedoch nur möglich, wenn man von neuen Sicherheitsannahmen ausgeht, deren gründliche Untersuchung noch aussteht. Wir beginnen diese Untersuchung, indem wir die Klasse von Berechnungsproblemen in Idealgittern mit ihrem allgemeineren Gegenstück in Bezug auf deren Größe vergleichen. Wir finden in den praxisrelevanten Gitterkategorien, in Übereinstimmung mit allgemeinen Vermutungen, heraus, dass die Anzahl der beschränkten Instanzen unter allen Instanzen asymptotisch vernachlässigbar ist. Das zweite offene Problem betrifft die Berechnungsprobleme im Average-Case, die als direkte Sicherheitsgrundlage vieler praktischer Verfahren dienen. Es ist bekannt, dass diese Probleme asymptotisch mindestens so schwer wie verwandte Worst-Case-Probleme sind, aber darüber hinaus ist wenig über ihre Robustheit gegenüber praktischen Angriffen bekannt. Insbesondere gibt es praxisrelevante Parameter, für die alle bekannten Algorithmen die entsprechenden Average-Case-Probleme nicht lösen können, die zugehörigen Worst-Case-Probleme aber teilweise schon. In den meisten Fällen hat diese Wissenslücke dazu geführt, dass beim Vorstellen neuer Gitterverfahren die Parameter entweder sehr konservativ ausgewählt oder überhaupt nicht angegeben wurden. Dies wiederum macht es unmöglich, die entsprechenden Verfahren mit Konkurrenten zu vergleichen, die auf anderen Paradigmen basieren. Wir erweitern das Verständnis der praktischen Sicherheit mehrerer verbreiteter kryptographischer Verfahren und verbessern gleichzeitig deren Effizienz. Unter anderem finden wir heraus, dass für die Kompressionsfunktion SWIFFT die Lösung bestimmter sicherheitsrelevanter Probleme, die eng mit der Suche von Kollisionen zusammenhängen, leichter ist als bisher angenommen und empfehlen hinreichend effiziente Ersatzparameter mit denen das Problem den ursprünglichen Annahmen gerecht wird. Wir schlagen ein neues Zero-Knowledge-Identifikationsverfahren vor, dass unseres Wissens alle konkurrierenden Post-Quantum-Verfahren übertrifft, insbesondere auch solche Verfahren, die auf anderen Paradigmen basieren. Als vielleicht bedeutendstes Ergebnis tragen wir dazu dabei, die Effizienzlücke zwischen beweisbar sicheren Gitterverschlüsselungsverfahren und dem vielgepriesenen Ad-hoc-Verfahren NTRU zu verkleinern. Dies erreichen wir, indem wir viele der jüngeren Entwicklungen zu einem neuen beweisbar sicheren Design zusammenfassen und eine umfassende Analyse zu dessen praktischer Sicherheit durchführen, was zusammen einen bedeutenden Effizienzsprung bei gleichbleibender Sicherheit in der Praxis zur Folge hat.

German
URN: urn:nbn:de:tuda-tuprints-23877
Classification DDC: 000 Generalities, computers, information > 004 Computer science
500 Science and mathematics > 510 Mathematics
Divisions: 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
Date Deposited: 12 Jan 2011 10:35
Last Modified: 07 Dec 2012 11:59
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/2387
PPN: 230141021
Export:
Actions (login required)
View Item View Item