Description
Récemment Diem et Gaudry ont introduit indépendemment une méthode de résolution du DLP sur les courbes elliptiques définies sur un corps fini non premier K, de degré d'extension n > 1 sur le corps de base k. Cet algorithme repose sur le principe général du calcul d'indice. Une étape cruciale de cet algorithme nécessite de décomposer des points de la courbe E(K) selon une base de facteurs. C'est à dire, étant donné un point fixé R de E(K) trouver n points Pi, 0 < i < n+1, de la base de facteurs F (sous ensemble fixé de E(K)) tels que R = P1 + ... + Pn. Une méthode de résolution algébrique de ce problème consiste à modéliser cette somme sous forme d'un système polynomial et de le résoudre. À cette fin, Semaev introduit les polynômes de sommation qui projettent le problème de décomposition de points sur l'axe des abscisses. L'application d'une restriction de Weil de K à k sur un tel polynôme de sommation engendre un système à coefficients dans k à n équations et n inconnues, dont la résolution est équivalente à celle du problème de décomposition de point. Le coût de la résolution de ces systèmes est exponentiel en n et elle devient rapidement impossible. Il est donc nécessaire d'optimiser la résolution de ces systèmes. Un moyen est d'utiliser les symétries du problème de décomposition de points. Une symétrie naturelle de ce problème, lié à la commutativité de la loi de groupe sur les points de la courbe, est l'action du groupe symétrique Sn. Dans cet exposé, nous mettrons en évidence des symétries supplémentaires. Nous étudierons en particulier deux représentations de courbes -- les courbes d'Edwards et les intersections de Jacobi -- pour lesquelles ces nouvelles symétries se propagent sur les polynômes de sommation. Pour ces représentations, nous verrons également comment elles permettent de simplifier les systèmes polynomiaux à résoudre. Finalement nous présenterons quelques résultats pratiques montrant le gain apporté par l'utilisation des symétries.
Prochains exposés
-
CryptoVerif: a computationally-sound security protocol verifier
Orateur : Bruno Blanchet - Inria
CryptoVerif is a security protocol verifier sound in the computational model of cryptography. It produces proofs by sequences of games, like those done manually by cryptographers. It has an automatic proof strategy and can also be guided by the user. It provides a generic method for specifying security assumptions on many cryptographic primitives, and can prove secrecy, authentication, and[…]-
Cryptography
-
-
Structured-Seed Local Pseudorandom Generators and their Applications
Orateur : Nikolas Melissaris - IRIF
We introduce structured‑seed local pseudorandom generators (SSL-PRGs), pseudorandom generators whose seed is drawn from an efficiently sampleable, structured distribution rather than uniformly. This seemingly modest relaxation turns out to capture many known applications of local PRGs, yet it can be realized from a broader family of hardness assumptions. Our main technical contribution is a[…]-
Cryptography
-
-
Post-Quantum Public-Key Pseudorandom Correlation Functions for OT
Orateur : Mahshid Riahinia - ENS, CNRS
Public-Key Pseudorandom Correlation Functions (PK-PCF) are an exciting recent primitive introduced to enable fast secure computation. Despite significant advances in the group-based setting, success in the post-quantum regime has been much more limited. In this talk, I will introduce an efficient lattice-based PK-PCF for the string OT correlation. At the heart of our result lie several technical[…] -
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
-