Orientations and the supersingular endomorphism ring problem
| 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:40:17Z | |
| dc.date.available | 2024-04-04T02:40:17Z | |
| dc.date.issued | 2022-05-25 | |
| dc.date.conference | 2022-05-30 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191052 | |
| dc.description.abstractEn | We study two important families of problems in isogenybased cryptography and how they relate to each other: computing the endomorphism ring of supersingular elliptic curves, and inverting the action of class groups on oriented supersingular curves. We prove that these two families of problems are closely related through polynomialtime reductions, assuming the generalised Riemann hypothesis. We identify two classes of essentially equivalent problems. The first class corresponds to the problem of computing the endomorphism ring of oriented curves. The security of a large family of cryptosystems (such as CSIDH) reduces to (and sometimes from) this class, for which there are heuristic quantum algorithms running in subexponential time. The second class corresponds to computing the endomorphism ring of orientable curves. The security of essentially all isogeny-based cryptosystems reduces to (and sometimes from) this second class, for which the best known algorithms are still exponential. Some of our reductions not only generalise, but also strengthen previously known results. For instance, it was known that in the particular case of curves defined over $\mathbb{F}_p$, the security of CSIDH reduces to the endomorphism ring problem in subexponential time. Our reductions imply that the security of CSIDH is actually equivalent to the endomorphism ring problem, under polynomial time reductions (circumventing arguments that proved such reductions unlikely). | |
| 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.publisher | Springer International Publishing | |
| dc.publisher.location | Cham | |
| dc.source.title | Advances in Cryptology – EUROCRYPT 2022 | |
| dc.title.en | Orientations and the supersingular endomorphism ring problem | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1007/978-3-031-07082-2_13 | |
| dc.subject.hal | Informatique [cs]/Cryptographie et sécurité [cs.CR] | |
| dc.subject.hal | Mathématiques [math]/Théorie des nombres [math.NT] | |
| bordeaux.page | 345-371 | |
| bordeaux.volume | 13277 | |
| 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 | Advances in Cryptology -- Eurocrypt 2022 | |
| bordeaux.country | NO | |
| bordeaux.title.proceeding | Advances in Cryptology – EUROCRYPT 2022 | |
| bordeaux.conference.city | Trondheim | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-03799393 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.end | 2022-06-03 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-03799393v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Advances%20in%20Cryptology%20%E2%80%93%20EUROCRYPT%202022&rft.date=2022-05-25&rft.volume=13277&rft.spage=345-371&rft.epage=345-371&rft.au=WESOLOWSKI,%20Benjamin&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||