A trade-off between classical and quantum circuit size for an attack against CSIDH
We propose a heuristic algorithm to solve the underlying hard problem of the CSIDH cryptosystem (and other isogeny-based cryptosystems using elliptic curves with endomorphism ring isomorphic to an imaginary quadratic order 𝒪). Let Δ = Disc(𝒪) (in CSIDH, Δ = −4p for p the security parameter). Let 0 &...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2020-11-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2020-0070 |
| _version_ | 1817997857669513216 |
|---|---|
| author | Biasse Jean-François Bonnetain Xavier Pring Benjamin Schrottenloher André Youmans William |
| author_facet | Biasse Jean-François Bonnetain Xavier Pring Benjamin Schrottenloher André Youmans William |
| author_sort | Biasse Jean-François |
| collection | DOAJ |
| description | We propose a heuristic algorithm to solve the underlying hard problem of the CSIDH cryptosystem (and other isogeny-based cryptosystems using elliptic curves with endomorphism ring isomorphic to an imaginary quadratic order 𝒪). Let Δ = Disc(𝒪) (in CSIDH, Δ = −4p for p the security parameter). Let 0 < α < 1/2, our algorithm requires: |
| first_indexed | 2024-04-14T02:44:29Z |
| format | Article |
| id | doaj.art-3f4a6b592a034dc7aa26d51735aee5df |
| institution | Directory Open Access Journal |
| issn | 1862-2984 |
| language | English |
| last_indexed | 2024-04-14T02:44:29Z |
| publishDate | 2020-11-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-3f4a6b592a034dc7aa26d51735aee5df2022-12-22T02:16:36ZengDe GruyterJournal of Mathematical Cryptology1862-29842020-11-0115141710.1515/jmc-2020-0070jmc-2020-0070A trade-off between classical and quantum circuit size for an attack against CSIDHBiasse Jean-François0Bonnetain Xavier1Pring Benjamin2Schrottenloher André3Youmans William4University of South Florida, 4202 E Fowler Ave, Tampa, FL33620, United States of AmericaINRIA, 2 Rue Simone IFF, 75012Paris, FranceUniversity of South Florida, 4202 E Fowler Ave, Tampa, FL33620, United States of AmericaINRIA, 2 Rue Simone IFF, 75012Paris, FranceUniversity of South Florida, 4202 E Fowler Ave, Tampa, FL33620, United States of AmericaWe propose a heuristic algorithm to solve the underlying hard problem of the CSIDH cryptosystem (and other isogeny-based cryptosystems using elliptic curves with endomorphism ring isomorphic to an imaginary quadratic order 𝒪). Let Δ = Disc(𝒪) (in CSIDH, Δ = −4p for p the security parameter). Let 0 < α < 1/2, our algorithm requires:https://doi.org/10.1515/jmc-2020-0070isogeniesimaginary quadratic ordersquantum algorithmsdihedral hidden subgroup problemcsidh94a6068q1268q1581p6811y1614q05 |
| spellingShingle | Biasse Jean-François Bonnetain Xavier Pring Benjamin Schrottenloher André Youmans William A trade-off between classical and quantum circuit size for an attack against CSIDH Journal of Mathematical Cryptology isogenies imaginary quadratic orders quantum algorithms dihedral hidden subgroup problem csidh 94a60 68q12 68q15 81p68 11y16 14q05 |
| title | A trade-off between classical and quantum circuit size for an attack against CSIDH |
| title_full | A trade-off between classical and quantum circuit size for an attack against CSIDH |
| title_fullStr | A trade-off between classical and quantum circuit size for an attack against CSIDH |
| title_full_unstemmed | A trade-off between classical and quantum circuit size for an attack against CSIDH |
| title_short | A trade-off between classical and quantum circuit size for an attack against CSIDH |
| title_sort | trade off between classical and quantum circuit size for an attack against csidh |
| topic | isogenies imaginary quadratic orders quantum algorithms dihedral hidden subgroup problem csidh 94a60 68q12 68q15 81p68 11y16 14q05 |
| url | https://doi.org/10.1515/jmc-2020-0070 |
| work_keys_str_mv | AT biassejeanfrancois atradeoffbetweenclassicalandquantumcircuitsizeforanattackagainstcsidh AT bonnetainxavier atradeoffbetweenclassicalandquantumcircuitsizeforanattackagainstcsidh AT pringbenjamin atradeoffbetweenclassicalandquantumcircuitsizeforanattackagainstcsidh AT schrottenloherandre atradeoffbetweenclassicalandquantumcircuitsizeforanattackagainstcsidh AT youmanswilliam atradeoffbetweenclassicalandquantumcircuitsizeforanattackagainstcsidh AT biassejeanfrancois tradeoffbetweenclassicalandquantumcircuitsizeforanattackagainstcsidh AT bonnetainxavier tradeoffbetweenclassicalandquantumcircuitsizeforanattackagainstcsidh AT pringbenjamin tradeoffbetweenclassicalandquantumcircuitsizeforanattackagainstcsidh AT schrottenloherandre tradeoffbetweenclassicalandquantumcircuitsizeforanattackagainstcsidh AT youmanswilliam tradeoffbetweenclassicalandquantumcircuitsizeforanattackagainstcsidh |