On the Relation between Efficiency, Security, and Practicality of Structured Lattices in Cryptography

Dokumentenart:	Hochschulschrift der Universität Regensburg (Dissertation)
Open Access Art:	Primärpublikation
Datum:	25 Juni 2025
Begutachter (Erstgutachter):	Prof. Dr. Juliane Krämer und Prof. Dr. Joachim Rosenthal
Tag der Prüfung:	25 Februar 2025
Institutionen:	Informatik und Data Science > Fachbereich Grundlagen der Informatik > Datensicherheit und Kryptohraphie (Prof. Dr. Juliane Krämer)
Stichwörter / Keywords:	Post-Quantum Cryptography, Lattice-based Cryptography, Advanced Security Notions, Mathematical Cryptography
Dewey-Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke > 000 Allgemeines, Wissenschaft 000 Informatik, Informationswissenschaft, allgemeine Werke > 004 Informatik 500 Naturwissenschaften und Mathematik > 510 Mathematik
Status:	Veröffentlicht
Begutachtet:	Ja, diese Version wurde begutachtet
An der Universität Regensburg entstanden:	Zum Teil
Dokumenten-ID:	76671

Zusammenfassung (Englisch)

This thesis presents current research on the relations between efficiency and security in the theory and practical constructions of lattice-based cryptography. Lattice-based cryptography is the most established family of post-quantum cryptography and has an almost 30-year history. Its very nature allows for many constructions which are simultaneously efficient and rely on trustworthy ...

Zusammenfassung (Englisch)

This thesis presents current research on the relations between efficiency and security in the theory and practical constructions of lattice-based cryptography.

Lattice-based cryptography is the most established family of post-quantum cryptography and has an almost 30-year history.
Its very nature allows for many constructions which are simultaneously efficient and rely on trustworthy hardness
assumptions on lattices.
In this thesis, we contribute to the area of lattice-based cryptography in three directions.

First, the efficiency of lattice-based cryptography stems to a great extent from algebraic structures attached to the
lattices used in practice.
Structures can spawn risks that adversaries may exploit.
Therefore, having a good understanding of lattice problems in the presence of structures is crucial to guarantee
security.
Here, we approach this question in terms of a mathematical framework to expand the set of techniques that can be used to
analyze structured lattices and computational problems on those.

Second, cryptographic protocols are used ubiquitously in modern network infrastructures.
Therefore, it is important to ensure that in all use cases, the security is guaranteed.
However, cryptographic primitives can expose vulnerabilities even though they are secure with respect to standard
security models.
Such vulnerabilities can be caused through misuse on the protocol level.
We develop several notions for digital signatures that go beyond standard assumptions and have real-world
use cases.
Further, we analyze concrete schemes regarding their security with respect to these notions and conclude with a deeper
relational understanding of these additional security features.

Third, we provide new constructions based on lattice assumptions in two cases.
On the one hand, the basic functionality of identification becomes interesting in the context of side-channel security on resource-constrained devices.
We present an efficient and secure identification protocol that is, by design, easy to harden against physical attacks.
On the other hand, we analyze many constructions of sanitizable signature schemes and present a systemized account of their potential to be instantiated with lattices.
We explain various cryptographic building blocks and whether these can be built from lattices.
A particular focus lies on the construction of chameleon hash functions from lattices that provide collision
resistance in the presence of collision oracles, thus, giving a strong security guarantee.

Our results lead to new research questions:
First, the framework in which we analyze structured lattices has the potential to be used to further increase our understanding of lattice problems.
Second, new advanced security notions are being introduced in recent works that give additional security guarantees.
Corresponding schemes need to be analyzed regarding those notions.
Moreover, a formal method to ensure security with respect to such new notions may be developed, as has been done in
the case of signatures.
Finally, while lattices provide the most versatile tools to develop cryptographic applications, many constructions have
not yet been instantiated with lattices and are open to further research.

Übersetzung der Zusammenfassung (Deutsch)

Diese Dissertation präsentiert den Zusammenhang zwischen Effizienz, Sicherheit und Praktikalität in der gitterbasierten Kryptographie. Gitterbasierte Kryptographie hat eine etwa 30-jährige Geschichte und gehört zu dem Bereich der Post-Quanten Kryptographie, die am weitesten erforscht wurde. Insbesondere ist die Nutzung von strukturierten Gittern zur Effizienzsteigerung eine verbreitete ...

Übersetzung der Zusammenfassung (Deutsch)

Diese Dissertation präsentiert den Zusammenhang zwischen Effizienz, Sicherheit und Praktikalität in der gitterbasierten Kryptographie.

Gitterbasierte Kryptographie hat eine etwa 30-jährige Geschichte und gehört zu dem Bereich der Post-Quanten Kryptographie, die am weitesten erforscht wurde.

Insbesondere ist die Nutzung von strukturierten Gittern zur Effizienzsteigerung eine verbreitete Methode, welche auf fortgeschrittenen mathematischen Grundlangen beruht.

In dieser Dissertation analysieren wir die Sicherheit kryptographischer Protokolle basierend auf strukturierten Gittern aus verschiedenen Perspektiven und benutzen solche Gitter, um effiziente und praktische Protokolle zu definieren.
Die Sicherheit bezieht sich dabei zum einen auf die mathematische Sicherheit der unterliegenden Berechnungsprobleme und andererseits auf Sicherheitseigenschaften der Protokolle in komplexen Anwendungszusammenhängen.
Die praktischen Protokolle dienen zur Anwendung in konkreten Situationen, die bisher nicht in der selben Effizienz bzw. nicht auf Post-Quanten Annahmen basierend möglich waren.

Details

Vorschau

Bibliographische Daten exportieren

Zusammenfassung (Englisch)

Zusammenfassung (Englisch)

Übersetzung der Zusammenfassung (Deutsch)

Übersetzung der Zusammenfassung (Deutsch)

Downloadstatistik

Downloads

Weitere Literatur (mittels CORE)

Universitätsbibliothek