Liens transverses ENS de Lyon

Agenda de l'ENS de Lyon

Réseaux idéaux et fonction multilinéaire GGH13 - On ideal lattices and the GGH13 multilinear map

Date
mer 16 oct 2019
Horaires

14H00

Intervenant(s)

Soutenance de thèse de Mme Alice PELLET--MARY du LIP, sous la direction de M. Damien STEHLE

Langue(s) des interventions

Description générale

La cryptographie à base de réseaux euclidiens est un domaine prometteur pour la construction de primitives cryptographiques post-quantiques. Un problème fondamental, lié aux réseaux, est le problème du plus court vecteur (ou SVP, pour Shortest Vector Problem). Ce problème est supposé être difficile à résoudre même avec un ordinateur quantique. Afin de gagner en efficacité, on peut utiliser des réseaux structurés, comme par exemple des réseaux idéaux ou des réseaux modules (qui sont une généralisation des réseaux idéaux). La sécurité de la plupart des schémas utilisant des réseaux structurés dépend de la difficulté du problème SVP dans des réseaux modules, mais un petit nombre de schémas peuvent également être impactés par SVP dans des réseaux idéaux. La principale construction pouvant être impactée par SVP dans des réseaux idéaux est la fonction multilinéaire GGH13.

Dans cette thèse, nous nous intéressons dans un premier temps au problème SVP dans les réseaux idéaux et modules. Nous présentons deux algorithmes permettant de résoudre SVP dans des réseaux idéaux et dans des modules de rang 2 plus rapidement que le meilleur algorithme connu pour des réseaux arbitraires. Le premier algorithme nécessite un pré-calcul exponentiel et le second a besoin d'avoir accès à un oracle résolvant le problème du plus proche vecteur dans un réseau fixé.

Dans un second temps, nous nous intéressons à la fonction GGH13 et à ses applications. Nous étudions d'abord l'impact des attaques statistiques sur la fonction GGH13 et ses variantes. Puis nous nous intéressons à la sécurité des obfuscateurs utilisant GGH13 et proposons une attaque quantique contre plusieurs de ces obfuscateurs.

Lattice-based cryptography is a promising area for constructing cryptographic primitives that are plausibly secure even in the presence of quantum computers. A fundamental problem related to lattices is the shortest vector problem (or SVP), which asks to find a shortest non-zero vector in a lattice. This problem is believed to be intractable, even quantumly. Structured lattices, for example ideal lattices or module lattices (the latter being a generalization of the former), are often used to improve the efficiency of lattice-based primitives. The security of most of the schemes based on structured lattices is related to SVP in module lattices, and a very small number of schemes can also be impacted by SVP in ideal lattices (which is a special case of SVP in module lattices). The main scheme whose security might be impacted by SVP in ideal lattices is the GGH13 map.

In this thesis, we first focus on the problem of finding short vectors in ideal and module lattices. We propose an algorithm which, after some exponential pre-computation, performs better on ideal lattices than the best known algorithm for arbitrary lattices. We also present an algorithm to find short vectors in rank 2 modules, provided that we have access to some oracle solving the closest vector problem in a fixed lattice.
 
In a second part of this thesis, we focus on the GGH13 map and its application to obfuscation. We first study the impact of statistical attacks on the GGH13 map and on its variants. We then study the security of obfuscators based on the GGH13 map and propose a quantum attack against multiple such obfuscators.

Gratuit
Mots clés
Disciplines