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

Item type:	Thesis of the University of Regensburg (PhD)
Open Access Type:	Primary Publication
Date:	25 June 2025
Referee:	Prof. Dr. Juliane Krämer and Prof. Dr. Joachim Rosenthal
Date of exam:	25 February 2025
Institutions:	Informatics and Data Science > Department Foundation of Computer Science > Datensicherheit und Kryptohraphie (Prof. Dr. Juliane Krämer)
Keywords:	Post-Quantum Cryptography, Lattice-based Cryptography, Advanced Security Notions, Mathematical Cryptography
Dewey Decimal Classification:	000 Computer science, information & general works > 000 Generalities, Science 000 Computer science, information & general works > 004 Computer science 500 Science > 510 Mathematics
Status:	Published
Refereed:	Yes, this version has been refereed
Created at the University of Regensburg:	Partially
Item ID:	76671

Abstract (English)

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 ...

Abstract (English)

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.

Translation of the abstract (German)

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 ...

Translation of the abstract (German)

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

Preview

Export bibliographical data

Abstract (English)

Abstract (English)

Translation of the abstract (German)

Translation of the abstract (German)

Download Statistics

Downloads

More literature (via CORE)

University Library