| Title: |
The supersingular endomorphism ring problem given one endomorphism |
| Authors: |
Herlédan Le Merdy, Arthur; Wesolowski, Benjamin |
| Contributors: |
Laboratoire de l'Informatique du Parallélisme (LIP); École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL); Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); Unité de Mathématiques Pures et Appliquées (UMPA-ENSL); École normale supérieure de Lyon (ENS de Lyon)-Centre National de la Recherche Scientifique (CNRS); ANR-21-CE94-0003,CHARM,Sécurité cryptographique des réseaux modules(2021); ANR-22-PETQ-0008,PQ-TLS,Post-quantum padlock for web browser(2022) |
| Source: |
https://hal.science/hal-04212227 ; 2023. |
| Publisher Information: |
HAL CCSD |
| Publication Year: |
2023 |
| Collection: |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
| Subject Terms: |
Isogeny-based cryptography; Endomorphism ring; Supersingular elliptic curve; Orientation; Class group; Cryptanalysis; [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR]; [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT] |
| Description: |
Given a supersingular elliptic curve E and a non-scalar endomorphism α of E, we prove that the endomorphism ring of E can be computed in classical time about disc(Z[α])^1/4 , and in quantum subexponential time, assuming the generalised Riemann hypothesis. Previous results either had higher complexities, or relied on heuristic assumptions. Along the way, we prove that the Primitivisation problem can be solved in polynomial time (a problem previously believed to be hard), and we prove that the action of smooth ideals on oriented elliptic curves can be computed in polynomial time (previous results of this form required the ideal to be powersmooth, i.e., not divisible by any large prime power). Following the attacks on SIDH, isogenies in high dimension are a central ingredient of our results. |
| Document Type: |
report |
| Language: |
English |
| Relation: |
info:eu-repo/semantics/altIdentifier/arxiv/2309.11912; hal-04212227; https://hal.science/hal-04212227; https://hal.science/hal-04212227v2/document; https://hal.science/hal-04212227v2/file/paper.pdf; ARXIV: 2309.11912 |
| Availability: |
https://hal.science/hal-04212227; https://hal.science/hal-04212227v2/document; https://hal.science/hal-04212227v2/file/paper.pdf |
| Rights: |
http://creativecommons.org/licenses/by/ ; info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.95D523CB |
| Database: |
BASE |