Description
Le problème (SVP) de trouver un vecteur non nul le plus court d'un réseau de $\R^n$ de dimension $d$ est un problème très classique ; au cours des dix dernières années, de nombreux travaux ont montré des bornes inférieures sur la complexité de ce problème. Ces résultats sont à la base des arguments de sécurité d'un certain nombre de cryptosystèmes (Ajtai-Dwork, NTRU). Le meilleur algorithme pratique pour ce problème, dû à Kannan, consiste à énumérer des points dans un ellipsoïde. Son analyse consiste classiquement à borner le nombre de points par le volume, qui est à son tour estimé par le volume du pavé circonscrit, donnant une complexité de $\tilde{O}(d^{d/2(1+o(1))})$. Nous montrons qu'une analyse plus fine conduit \`a une complexit\'e de $\tilde{O}(d^{d/(2e)(1+o(1))})$; ce résultat permet également d'améliorer la complexité des algorithmes de recherche du vecteur le plus proche (CVP), ou de calcul de bases "blocs-réduites" à la Schnorr.
Next sessions
-
!!! Reporté !!! Encryption homomorphe sans bruit à l'aide de groupes
Speaker : Pierre Guillot - Ravel Technologies (dispo Université de Strasbourg, IRMA)
Je vais rappeler les travaux de Nuida et Ostrovski sur l'utilisation des groupes pour l'élaboration de schémas cryptographiques homomorphes. Je vais présenter nos travaux qui fournissent des encodages à la fois plus efficaces et plus généraux, et qui déterminent exactement quels groupes peuvent être utilisés. Puis je vais discuter GRAFHEN, un protocole qui utilise ces idées. Je dirai juste[…]-
Cryptography
-
-
MIKE: An efficient and compact NIKE Based on a Commutative Monoidal Action
Speaker : Jonathan Komada Eriksen - COSIC, KU Leuven
Robert recently described a powerful correspondence between certain (Hermitian) modules and (polarized) abelian varieties, which simultaneously generalizes both the class-group action underlying protocols such as CSIDH, and the Deuring correspondence, underlying protocols such as SQIsign. Using this correspondence, he also proposed how to construct a post-quantum NIKE, called MIKE, which, at a[…]-
Cryptography
-