Description
Résumé : Le générateur sac-à-dos, présenté en 1985 est un générateur pseudo aléatoire annoncé sécurisé qui combine un générateur pseudo aléatoire non sécurisé et un problème dur. Une erreur de design repérée en 2011 permet à W. Meier et S. Knellwolf de retrouver une partie du secret mais les explications théoriques et heuristiques sont partielles. Dans cet exposé, je vais présenter une nouvelle attaque contre ce générateur qui exploite la même faiblesse que l'attaque de 2011 mais qui met à jour, de manière beaucoup plus directe, le lien entre le problème à résoudre et les réseaux euclidiens. Grâce à cette meilleure compréhension, la nouvelle attaque retrouve une plus grande partie du secret et sur une plus grande plage de paramètres, pour un coût similaire.
Abstract: The knapsack generator, presented in 1985, is a pseudorandom generator announced as secure, that combines an insecure pseudorandom generator and a hard problem. A design error identified in 2011 allowed W. Meier and S. Knellwolf to recover part of the secret, but the theoretical and heuristic explanations are partial. In this talk, I will present a new attack against this generator that exploits the same weakness as the 2011 attack but that reveals, in a much more direct way, the link between the problem to be solved and Euclidean lattices. Thanks to this better understanding, the new attack recovers a larger part of the secret and on a larger range of parameters, for a similar cost.
Infos pratiques
Prochains exposés
-
Predicting Module-Lattice Reduction
Orateur : Paola de Perthuis - CWI
Is module-lattice reduction better than unstructured lattice reduction? This question was highlighted as `Q8' in the Kyber NIST standardization submission (Avanzi et al., 2021), as potentially affecting the concrete security of Kyber and other module-lattice-based schemes. Foundational works on module-lattice reduction (Lee, Pellet-Mary, Stehlé, and Wallet, ASIACRYPT 2019; Mukherjee and Stephens[…]-
Cryptography
-
-
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
Orateur : 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
-