The supersingular isogeny path and endomorphism ring problems are equivalent
| hal.structure.identifier | Lithe and fast algorithmic number theory [LFANT] | |
| hal.structure.identifier | Centre National de la Recherche Scientifique [CNRS] | |
| dc.contributor.author | WESOLOWSKI, Benjamin | |
| dc.date.accessioned | 2024-04-04T02:45:41Z | |
| dc.date.available | 2024-04-04T02:45:41Z | |
| dc.date.conference | 2022-02-07 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191487 | |
| dc.description.abstractEn | We prove that the path-finding problem in isogeny graphs and the endomorphism ring problem for supersingular elliptic curves are equivalent under reductions of polynomial expected time, assuming the generalised Riemann hypothesis. The presumed hardness of these problems is foundational for isogeny-based cryptography. As an essential tool, we develop a rigorous algorithm for the quaternion analog of the path-finding problem, building upon the heuristic method of Kohel, Lauter, Petit and Tignol. This problem, and its (previously heuristic) resolution, are both a powerful cryptanalytic tool and a building-block for cryptosystems. | |
| dc.description.sponsorship | Méthodes pour les variétés abéliennes de petite dimension - ANR-20-CE40-0013 | |
| dc.description.sponsorship | Cryptographie, isogenies et variété abéliennes surpuissantes - ANR-19-CE48-0008 | |
| dc.language.iso | en | |
| dc.title.en | The supersingular isogeny path and endomorphism ring problems are equivalent | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Informatique [cs]/Cryptographie et sécurité [cs.CR] | |
| dc.subject.hal | Mathématiques [math]/Géométrie algébrique [math.AG] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | FOCS 2021 - 62nd Annual IEEE Symposium on Foundations of Computer Science | |
| bordeaux.country | US | |
| bordeaux.conference.city | Denver, Colorado | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-03340899 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.end | 2022-02-10 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-03340899v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=WESOLOWSKI,%20Benjamin&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||