Solving Elliptic Curve Discrete Logarithm Problem on Twisted Edwards Curves Using Quantum Annealing and Index Calculus Method

[1] AMADORI, A.—PINTORE, F.—SALA, M.: On the discrete logarithm problem for prime-field elliptic curves, Finite Fields and Their Applications 51 (2018), 168–182. Search in Google Scholar

[2] BERNSTEIN, D. J.—BIRKNER, P.—JOYE, M.—LANGE, T.—PETERS, C.: Twisted Edwards Curves.In: Progress in Cryptology — AFRICACRYPT 2008 (S. Vaudenay, ed.), Springer-Verlag, Berlin 2008, pp. 389–405. Search in Google Scholar

[3] BERNSTEIN, D. J.—LANGE, T.: Faster Addition and Doubling on Elliptic Curves. In: Advances in Cryptology — ASIACRYPT 2007 (K. Kurosawa, ed.), Springer-Verlag, Berlin, 2007. Search in Google Scholar

[4] BETTALE, L.—FAUGERE, J.-C.—PERRET, L.: Hybrid approach for solving multivariate systems over finite fields,J. Math. Cryptol. 3 (2009), 177–197. Search in Google Scholar

[5] BUREK, E.—WROŃSKI, M.—MAŃK, K.—MISZTAL, M.: Algebraic attacks on block ciphers using quantum annealing, IEEE Transactions on Emerging Topics in Computing 10 (2022), 678–689. Search in Google Scholar

[6] CHEN, Y.-A.—GAO, X.-S.: Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems, J. Syst. Sci. Complex. 35 (2022), 373–412. Search in Google Scholar

[7] CHEN, Y.-A.—GAO, X.-S.—YUAN, C.-M.: Quantum algorithm for optimization and polynomial system solving over finite field and application to cryptanalysis,arXivpreprint arXiv:1802.03856, 2018. Search in Google Scholar

[8] DIEM, C.: The GHS attack in odd characteristic, J. Ramanujan Math. Soc. 18 (2003), 1–32. Search in Google Scholar

[9] DIEM, C.: On the discrete logarithm problem in elliptic curves, Compos. Math.147 (2011), 75–104. Search in Google Scholar

[10] DRIDI, R.—ALGHASSI, H.: Prime factorization using quantum annealing and computational algebraic geometry, Scientific Reports 7, Article no. 43048 (2017), 1–10; https://doi.org/10.1038/srep43048 Search in Google Scholar

[11] DRY LO, R.—KIJKO, T.—WROŃSKI, M.: Determining formulas related to point compression on alternative models of elliptic curves, Fundamenta Informaticae 169 (2019), 285–294. Search in Google Scholar

[12] EDWARDS, H. M.: A normal form for elliptic curves, Bull. Amer. Math. Soc. 44 (2007), 393–422. Search in Google Scholar

[13] FAUGÈRE, J.-C.—GAUDRY, P.—HUOT, L.—RENAULT, G.: Using symmetries in the index calculus for elliptic curves discrete logarithm, J. Cryptology 27 (2014), 595–635. Search in Google Scholar

[14] GAUDRY, P.: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem, Journal of Symbolic Computation 44 (2009), 1690–1702. Search in Google Scholar

[15] JIANG, S.—BRITT, K. A.—MCCASKEY, A. J.—HUMBLE, T. S.—KAIS, S.: Quantum annealing for prime factorization, Scientific Reports 8 (2018), 1–9; https://doi.org/10.1038/s41598-018-36058-z Search in Google Scholar

[16] KUDO, M.—YOKOTA, Y.—TAKAHASHI, Y.—YASUDA, M.: Acceleration of index calculus for solving ECDLP over prime fields and its limitation.In: Cryptology and Network Security (J. Camenisch, P. Papadimitratos, eds.), Springer International Publishing. Cham, 2018. pp. 377–393. Search in Google Scholar

[17] LENSTRA JR, H. W.: Factoring integers with elliptic curves, Ann. Math. (1987), 649–673. Search in Google Scholar

[18] MONTGOMERY, P. L.: Speeding the Pollard and elliptic curve methods of factorization, Math. Comput. 48 (1987), 243–264. Search in Google Scholar

[19] PETIT, C.—KOSTERS, M.—MESSENG, A.: Algebraic approaches for the elliptic curve discrete logarithm problem over prime fields,In: Public-Key Cryptography — PKC 2016 (C.-M. Cheng, K.-M. Chung, G. Persiano, B.-Y. Yang, eds.), Springer-Verlag, Berlin, 2016, pp. 3–18. Search in Google Scholar

[20] SEMAEV, I.: Summation polynomials and the discrete logarithm problem on elliptic curves, Cryptology ePrint Archive, Paper 2004/031, (2004); https://ia.cr/2004/031 Search in Google Scholar

[21] WANG, B.—HU, F.—YAO, H.—WANG, C.: Prime factorization algorithm based on parameter optimization of Ising model, Scientific Reports 10 (2020), 1–10; https://doi.org/10.1038/s41598-020-62802-5 Search in Google Scholar

[22] WROŃSKI, M.: Index calculus method for solving elliptic curve discrete logarithm problem using quantum annealing.In: International Conference on Computational Science, Springer-Verlag, 2021. pp. 149–155. Search in Google Scholar

[23] WROŃSKI, M.: Index calculus method for solving elliptic curve discrete logarithm problem using quantum annealing - example 2021; https://github.com/Michal-Wronski/ECDLP-index-calculus-using-QUBO Search in Google Scholar

[24] WROŃSKI, M.: Practical solving of discrete logarithm problem over prime fields using quantum annealing. In: International Conference on Computational Science, Springer-Verlag, 2022, pp. 93–106. Search in Google Scholar