Description
The main focus of this PhD thesis lies on the computational problem Learning With Errors (LWE). It is a core building block of lattice-based cryptography, which itself is among the most promising candidates to replace current cryptographic protocols once large-scale quantum computers may be available. The contributions of the present work are separated into two different parts. First, we study the hardness of structured variants of LWE. To this end, we show that under suitable parameter choices the Module Learning With Errors (M-LWE) problem doesn't become significantly easier to solve even if the underlying secret is replaced by a binary vector. Furthermore, we provide a classical hardness reduction for M-LWE, which further strengthens our confidence in its suitability for cryptography. Additionally, we define a new hardness assumption, the Middle-Product Computational Learning With Rounding (MP-CLWR) problem, which inherits the advantages of two existing LWE variants. Finally, we study problems related to the partial Vandermonde matrix. This is a recent source of hardness assumptions for lattice-based cryptography and its rigorous study is important to gain trust in it. In the second part of this manuscript, we show that the new hardness assumptions we introduced before serve for the construction of efficient public-key encryption. On the one hand, we design a new encryption scheme, whose security is provably based on the MP-CLWR problem. On the other hand, we modify an existing encryption scheme, called PASS Encrypt, to provide it with a security proof based on two explicitly stated partial Vandermonde problems.<br/> lien: https://youtu.be/Bu_PWWb63iU
Next sessions
-
Verification of Rust Cryptographic Implementations with Aeneas
Speaker : Aymeric Fromherz - Inria
From secure communications to online banking, cryptography is the cornerstone of most modern secure applications. Unfortunately, cryptographic design and implementation is notoriously error-prone, with a long history of design flaws, implementation bugs, and high-profile attacks. To address this issue, several projects proposed the use of formal verification techniques to statically ensure the[…] -
On the average hardness of SIVP for module lattices of fixed rank
Speaker : Radu Toma - Sorbonne Université
In joint work with Koen de Boer, Aurel Page, and Benjamin Wesolowski, we study the hardness of the approximate Shortest Independent Vectors Problem (SIVP) for random module lattices. We use here a natural notion of randomness as defined originally by Siegel through Haar measures. By proving a reduction, we show it is essentially as hard as the problem for arbitrary instances. While this was[…] -
Endomorphisms via Splittings
Speaker : Min-Yi Shen - No Affiliation
One of the fundamental hardness assumptions underlying isogeny-based cryptography is the problem of finding a non-trivial endomorphism of a given supersingular elliptic curve. In this talk, we show that the problem is related to the problem of finding a splitting of a principally polarised superspecial abelian surface. In particular, we provide formal security reductions and a proof-of-concept[…]-
Cryptography
-