TU Darmstadt / ULB / TUprints

On the Design and Improvement of Lattice-based Cryptosystems

El Bansarkhani, Rachid (2015)
On the Design and Improvement of Lattice-based Cryptosystems.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
Dissertation.pdf
Copyright Information: CC BY-NC-ND 3.0 Unported - Creative Commons, Attribution, NonCommercial, NoDerivs.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: On the Design and Improvement of Lattice-based Cryptosystems
Language: English
Referees: Buchmann, Prof. Dr. Johannes ; Güneysu, Prof. Dr. Tim
Date: 10 June 2015
Place of Publication: Darmstadt
Date of oral examination: 10 June 2015
Abstract:

Digital signatures and encryption schemes constitute arguably an integral part of cryptographic schemes with the goal to meet the security needs of present and future private and business applications. However, almost all public key cryptosystems applied in practice are put at risk due to its vulnerability to quantum attacks as a result of Shor's quantum algorithm. The magnitude of economic and social impact is tremendous inherently asking for alternatives replacing classical schemes in case large-scale quantum computers are built. Lattice-based cryptography emerged as a powerful candidate attracting lots of attention not only due to its conjectured resistance against quantum attacks, but also because of its unique security guarantee to provide worst-case hardness of average-case instances. Hence, the requirement of imposing further assumptions on the hardness of randomly chosen instances disappears, resulting in more efficient instantiations of cryptographic schemes. The best known lattice attack algorithms run in exponential time. In this thesis we contribute to a smooth transition into a world with practically efficient lattice-based cryptographic schemes. This is indeed accomplished by designing new algorithms and cryptographic schemes as well as improving existing ones. Our contributions are threefold. First, we construct new encryption schemes that fully exploit the error term in LWE instances. To this end, we introduce a novel computational problem that we call Augmented LWE (A-LWE), differing from the original LWE problem only in the way the error term is produced. In fact, we embed arbitrary data into the error term without changing the target distributions. Following this, we prove that A-LWE instances are indistinguishable from LWE samples. This allows to build powerful encryption schemes on top of the A-LWE problem that are simple in its representations and efficient in practice while encrypting huge amounts of data realizing message expansion factors close to 1. This improves, to our knowledge, upon all existing encryption schemes. Due to the versatility of the error term, we further add various security features such as CCA and RCCA security or even plug lattice-based signatures into parts of the error term, thus providing an additional mechanism to authenticate encrypted data. Based on the methodology to embed arbitrary data into the error term while keeping the target distributions, we realize a novel CDT-like discrete Gaussian sampler that beats the best known samplers such as Knuth-Yao or the standard CDT sampler in terms of running time. At run time the table size amounting to 44 elements is constant for every discrete Gaussian parameter and the total space requirements are exactly as large as for the standard CDT sampler. Further results include a very efficient inversion algorithm for ring elements in special classes of cyclotomic rings. In fact, by use of the NTT it is possible to efficiently check for invertibility and deduce a representation of the corresponding unit group. Moreover, we generalize the LWE inversion algorithm for the trapdoor candidate of Micciancio and Peikert from power of two moduli to arbitrary composed integers using a different approach. In the second part of this thesis, we present an efficient trapdoor construction for ideal lattices and an associated description of the GPV signature scheme. Furthermore, we improve the signing step using a different representation of the involved perturbation matrix leading to enhanced memory usage and running times. Subsequently, we introduce an advanced compression algorithm for GPV signatures, which previously suffered from huge signature sizes as a result of the construction or due to the requirement of the security proof. We circumvent this problem by introducing the notion of public and secret randomness for signatures. In particular, we generate the public portion of a signature from a short uniform random seed without violating the previous conditions. This concept is subsequently transferred to the multi-signer setting which increases the efficiency of the compression scheme in presence of multiple signers. Finally in this part, we propose the first lattice-based sequential aggregate signature scheme that enables a group of signers to sequentially generate an aggregate signature of reduced storage size such that the verifier is still able to check that each signer indeed signed a message. This approach is realized based on lattice-based trapdoor functions and has many application areas such as wireless sensor networks. In the final part of this thesis, we extend the theoretical foundations of lattices and propose new representations of lattice problems by use of Cauchy integrals. Considering lattice points as simple poles of some complex functions allows to operate on lattice points via Cauchy integrals and its generalizations. For instance, we can deduce for the one-dimensional and two-dimensional case simple expressions for the number of lattice points inside a domain using trigonometric or elliptic functions.

Alternative Abstract:
Alternative AbstractLanguage

Digitale Signatur- und Verschlüsselungsalgorithmen bilden einen wesentlichen Bestandteil von kryptografischen Verfahren mit dem Ziel, die Sicherheitsbedürfnisse von gegenwärtigen und zukünftigen Privat- und Geschäftsanwendungen zu erfüllen. Jedoch sind alle in der Praxis eingesetzten asymmetrischen Verfahren aufgrund der Anfälligkeit für Quantencomputer-Angriffe infolge Shors Quantenalgorithmus gefährdet. Das Ausmaß der wirtschaftlichen und gesellschaftlichen Auswirkungen sind gewaltig, wodurch unmittelbar die Forderung nach Alternativen besteht, die klassische Systeme ersetzen, sobald Quantencomputer im großen Maßstab hergestellt werden können. Gitterbasierte Kryptografie ist als leistungsstarke Alternative hervorgetreten, die die Aufmerksamkeit der Forscher nicht nur wegen der vermuteten Resistenz gegen Quantencomputer-Angriffe auf sich zieht, sondern auch wegen ihrer einzigartigen Sicherheitsgarantie der Worst-Case-Härte von Average-Case-Instanzen. Auf diese Weise entfällt die Notwendigkeit, gesonderte Annahmen über die Average-Case Härte zu formulieren, sodass praktische Instanziierungen in der Tat Sicherheitsgarantien von Worst-Case-Instanzen genießen. Die bekanntesten Gitterangriffsalgorithmen laufen mit exponentieller Zeitkomplexität. In dieser Arbeit tragen wir zu einem reibungslosen übergang in eine Welt mit praktikablen gitterbasierten Verfahren bei. Dies wird durch die Entwicklung von neuen Algorithmen und kryptographischen Verfahren sowie die Verbesserung bestehender erreicht. Unsere Beiträge sind dreigeteilt. Erstens, wir stellen neue Verschlüsselungsverfahren vor, die den Fehlerterm bei LWE-Instanzen vollständig ausschöpfen, um den Nachrichtendurchsatz signifikant zu erhöhen. Zu diesem Zweck führen wir ein neues Berechnungsproblem ein, das wir als Augmented LWE (A-LWE) bezeichnen und das sich vom ursprünglichen LWE-Problem nur in der Weise unterscheidet, wie der Fehlerterm erzeugt wird. In der Tat können beliebige Daten in den Fehlerterm eingebettet werden, ohne die Zielverteilungen zu verändern. Im Anschluss daran erfolgt ein Beweis, dass A-LWE-Instanzen ununterscheidbar von LWE-Instanzen sind und demnach auf der Schwierigkeit des LWE-Problems beruhen. Dies erlaubt es, leistungsstarke Verschlüsselungsverfahren auf Grundlage des A-LWE-Problems zu konstruieren, die einfach in der Darstellung und effizient in der Praxis sind, während gleichzeitig große Datenmengen verschlüsselt werden können, sodass Nachrichten-Expansionsfaktoren nahe 1 praktisch erreicht werden. Dies verbessert unseres Wissens nach alle bestehenden Verschlüsselungsverfahren. Aufgrund der Vielseitigkeit des Fehlerterms können weitere Zusatzeigenschaften hinzugefügt werden wie etwa CCA- bzw. RCCA-Sicherheit. Aber auch gitterbasierte Signaturen können als Teil des Fehlerterms fungieren und erweitern somit das Verschlüsselungsverfahren um einen weiteren Mechanismus, der die Authentifikation von verschlüsselten Daten auf einfache Weise realisiert. Die Methodik zur Erzeugung des Fehlerterms bei A-LWE-Instanzen hat ebenfalls einen konzeptuell neuen und effizienten Diskret-Gauß-Sampler hervorgebracht, der die bekanntesten Verfahren, wie z.B. Knuth-Yao oder den CDT-Sampler auf Basis der Inversionsmethode, in Bezug auf die Leistungsfähigkeit übertrifft. Zur Laufzeit wird ein Wert von einer Tabelle der konstanten Größe von maximal 44 Elementen für beliebige Gauß-Parameter gesampelt. Der Gesamtspeicherbedarf beläuft sich auf die Größe der Tabelle beim bekannten CDT-Sampler. Weitere Ergebnisse beinhalten einen sehr effizienten Inversionsalgorithmus für Ringelemente in speziellen Klassen von Kreisteilungsringen. Durch die Verwendung der NTT ist es möglich, die Existenz von Inversen zu gegebenen Ringelementen effizient zu überprüfen und zu bestimmen. Eine Darstellung der entsprechenden Einheitengruppe lässt sich auf diese Weise unkompliziert und anschaulich ermitteln. Außerdem verallgemeinern wir den LWE-Inversionsalgorithmus für die Falltürkonstruktion von Micciancio und Peikert von Zweierpotenz-Moduli auf beliebig zusammengesetzte Zahlen. Im zweiten Teil dieser Arbeit präsentieren wir eine effiziente Falltürkonstruktion für Ideal-Gitter und eine zugehörige Beschreibung des GPV-Signaturverfahrens. Durch eine verbesserte Darstellung der assoziierten Fehlermatrix kann der Signiervorgang im Vergleich zur ursprünglichen Arbeit erheblich vereinfacht werden. Dies wirkt sich unmittelbar durch eine stark optimierte Speichernutzung und Laufzeit aus. Anschließend schlagen wir einen neuartigen Kompressionsalgorithmus für GPV-Signaturen vor, die bisher als Ergebnis der Falltürkonstruktion bzw. der Anforderungen des Sicherheitsbeweises einen zu hohen Speicherverbrauch aufwiesen. Wir umgehen dieses Problem mit der Einführung des Begriffs der öffentlichen und geheimen Zufälligkeit für Signaturen. Der öffentliche Teil einer Signatur kann demnach von einer kurzen und gleichverteilten Bitfolge erzeugt werden, ohne die vorherigen Bedingungen zu verletzen. Dieses Konzept wird anschließend auf die Situation mit mehreren Teilnehmern erweitert, wodurch sich die Effizienz und der Wirkungsgrad des Kompressionsverfahrens erhöht. Schließlich schlagen wir das erste gitterbasierte und sequenzielle Aggregationsverfahren für Signaturen vor, das einer Gruppe von Teilnehmern ermöglicht, sequenziell eine aggregierte Signatur zu erzeugen, dessen Größe sich im Vergleich zur ursprünglichen Gesamtgröße aller Signaturen sehr stark reduziert hat. Der Prüfer ist jederzeit in der Lage zu verifizieren, dass jeder Teilnehmer eine Nachricht tatsächlich signiert hat. Dieser Ansatz wird mittels gitterbasierter Falltürkonstruktionen realisiert und hat viele Anwendungsbereiche. Im letzten Teil dieser Arbeit werden theoretische Aspekte von gitterbasierten Problemen behandelt. Es werden neue Repräsentationen bzw. Relationen von interessanten Gitterproblemen vorgestellt, die auf Basis von Cauchy-Integralen hergeleitet werden. Betrachtet man Gitterpunkte als einfache Pole von komplexen Funktionen, so ist es prinzipiell möglich über Cauchy Integrale und ihren Verallgemeinerungen auf Gitterpunkte zu operieren. Beispielsweise lassen sich für den ein- und zweidimensionalen Fall, ebenfalls relevante Szenarien in kryptografischen Anwendungen, einfache Ausdrücke bzw. Formeln für die Anzahl von Gitterpunkten in einem Gebiet via trigonometrischen und elliptischen Funktionen ableiten.

German
URN: urn:nbn:de:tuda-tuprints-49699
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
Date Deposited: 15 Sep 2015 08:52
Last Modified: 16 Sep 2015 07:50
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/4969
PPN: 386801258
Export:
Actions (login required)
View Item View Item