Description
La transformée de Fourier rapide (FFT) permet de calculer en temps quasilinéaire le produit de deux polynômes dans l'anneau de convolution R[x]/(xd-1), une tâche qui nécessiterait un temps quadratique de manière naïve. De manière équivalente, elle permet d'accélérer les produits matrice-vecteur quand la matrice est circulante. Dans nos travaux, nous montrons que les idées de la FFT peuvent être appliquées à l'orthogonalisation de matrices circulantes (par blocs de taille d*d). Lorsque d est friable, l'orthogonalisation de Gram-Schmidt (GSO) peut être réalisée de manière récursive, ce qui permet de calculer une représentation factorisée et creuse de la GSO de taille O(d log d). À son tour, cette décomposition de la GSO accélère un algorithme central sur les réseaux: l'algorithme Nearest Plane de Babai. Dans les deux cas, les complexités en temps et en espace de nos algorithmes sont en O(d log d).<br/> Nos résultats s'étendent aux anneaux cyclotomiques, ainsi qu'au sampler de Klein, une version probabiliste de l'algorithme nearest plane. La principale application est d'accélérer la cryptographie sur les réseaux euclidiens.
Next sessions
-
Séminaire C2 à INRIA Paris
Emmanuel Thomé et Pierrick Gaudry Rachelle Heim Boissier Épiphane Nouetowa Dung Bui Plus d'infos sur https://seminaire-c2.inria.fr/ -
Attacking the Supersingular Isogeny Problem: From the Delfs–Galbraith algorithm to oriented graphs
Speaker : Arthur Herlédan Le Merdy - COSIC, KU Leuven
The threat of quantum computers motivates the introduction of new hard problems for cryptography.One promising candidate is the Isogeny problem: given two elliptic curves, compute a “nice’’ map between them, called an isogeny.In this talk, we study classical attacks on this problem, specialised to supersingular elliptic curves, on which the security of current isogeny-based cryptography relies. In[…]-
Cryptography
-