The supersingular endomorphism ring problem given one endomorphism
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908435206897664 |
|---|---|
| author | Merdy, Arthur Herlédan Le Wesolowski, Benjamin |
| author_facet | Merdy, Arthur Herlédan Le Wesolowski, Benjamin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_11912 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The supersingular endomorphism ring problem given one endomorphism Merdy, Arthur Herlédan Le Wesolowski, Benjamin Cryptography and Security Number Theory 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. |
| title | The supersingular endomorphism ring problem given one endomorphism |
| topic | Cryptography and Security Number Theory |
| url | https://arxiv.org/abs/2309.11912 |