Trade-off between Performance and Security for Supersingular Isogeny-Based Cryptosystems

• Claudio Téllez LNCC
• Fábio Borges LNCC

DOI: https://doi.org/10.5753/sbseg.2018.4247

Resumo

Cryptosystems based on isogenies between supersingular elliptic curves are considered promising candidates for a post-quantum era. Their security is based on the intractability of the Computational Supersingular Isogeny Problem (CSSIP) and of the Decisional Supersingular Product Problem (DSSPP). For this reason, there have been many important breakthroughs in supersingular isogeny cryptography in recent years. The purpose of our work is to provide a complexity analysis of the trade-off between performance and security for supersingular isogeny-based cryptosystems (SSI) in comparison with Discrete Logarithm Problem (DLP) and Integer Factorization Problem (IFP). We show how the complexities increase for the attack algorithms when the key lengths become longer. As SSI achieves small key sizes at practical security levels, it is a strong potential quantum-resistant cryptosystem.

Referências

Adj, G., Cervantes-Vázquez, D., Chi-Domínguez, J.-J., Menezes, A., and Rodríguez-Henríquez, F. (2018). On the cost of computing isogenies between supersingular elliptic curves. IACR Cryptology ePrint Archive, 2018:313.

Alon, N. and Milman, V. D. (1985). λ1, isoperimetric inequalities for graphs, and super-concentrators. J. Combin. Theory Ser. B, 38(1):73–88.

Azarderakhsh, R., Jao, D., Kalach, K., Koziel, B., and Leonardi, C. (2016). Key compression for isogeny-based cryptosystems. In Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography, AsiaPKC ’16, pages 1–10, New York, NY, USA. ACM.

Barker, E. (2016). Recommendation for Key Management. Part 1: General. NIST Special Publication 800-57 Part 1 Revision 4 [Online]. Available: DOI: 10.6028/NIST.SP.800-57pt1r4 [January 2016]. National Institute of Standards and Technology, Gaithersburg, MD.

Borges, F., Lara, P., and Portugal, R. (2017). Parallel algorithms for modular multi-exponentiation. Appl. Math. Comput., 292(C):406–416.

Charles, D. X., Lauter, K. E., and Goren, E. Z. (2009). Cryptographic hash functions from expander graphs. Journal of Cryptology, 22(1):93–113.

Chen, L., Jordan, S., Liu, Y.-K., Moody, D., Peralta, R., and an Daniel Smith-Tone, R. P. (2016). NIST Report on Post-Quantum Cryptography NISTIR 8105 [Online]. Available: DOI: 10.6028/NIST.IR.8105 [April 2016]. National Institute of Standards and Technology, Gaithersburg, MD.

Childs, A. M., Jao, D., and Soukharev, V. (2010). Constructing elliptic curve isogenies in quantum subexponential time. CoRR, abs/1012.4019.

Costello, C., Jao, D., Longa, P., Naehrig, M., Renes, J., and Urbanik, D. (2017). Efficient compression of sidh public keys. In EUROCRYPT (1), pages 679–706. Springer.

Costello, C., Longa, P., and Naehrig, M. (2016). Efficient algorithms for supersingular isogeny diffie-hellman. In Proceedings, Part I, of the 36th Annual International Cryptology Conference on Advances in Cryptology — CRYPTO 2016 - Volume 9814, pages 572–601, Berlin, Heidelberg. Springer-Verlag.

Couveignes, J.-M., m. Couveignes, J., Dewaghe, L., Dewaghe, L., Morain, F., and Morain, F. (1996). Isogeny cycles and the schoof-elkies-atkin algorithm. In Research Report LIX/RR/96/03, LIX, page 96.

Deuring, M. (1941). Die Typen der Multiplikatorenringe elliptischer Funktionenkörper. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 14(1):197–272.

Dodziuk, J. (1984). Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Amer. Math. Soc., 284(2):787–794.

Elkies, N. D. (1998). Elliptic and modular curves over finite fields and related computational issues. In Computational perspectives on number theory (Chicago, IL, 1995), volume 7 of Studies in Advanced Mathematics, pages 21–76. AMS International Press.

Feo, L. D. (2017). Mathematics of isogeny based cryptography. CoRR, abs/1711.04062.

Feo, L. D., Jao, D., and Plût, J. (2011). Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Cryptology ePrint Archive, Report 2011/506. [link].

Galbraith, S. and Stolbunov, A. (2013). Improved algorithm for the isogeny problem for ordinary elliptic curves. Applicable Algebra in Engineering, Communication and Computing, 24(2):107–131.

Galbraith, S. D. (1999). Constructing isogenies between elliptic curves over finite fields. LMS J. Comput. Math, 2:118–138.

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, pages 212–219. ACM.

Hashimoto, Y. (2018). Multivariate public key cryptosystems. In Mathematical Modelling for Next-Generation Cryptography, pages 17–42. Springer.

Hermans, J., Vercauteren, F., and Preneel, B. (2010). Speed records for ntru. In Pieprzyk, J., editor, Topics in Cryptology - CT-RSA 2010, pages 73–88, Berlin, Heidelberg. Springer Berlin Heidelberg.

Hoory, S., Lilian, N., and Wigderson, A. (2006). Expander graphs and their applications. Bulletin (New Series) of the American Mathematical Society, 43(4):349–561.

Jao, D. and Feo, L. D. (2011). Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In Yang, B.-Y., editor, Post-Quantum Cryptography, pages 19–34. Springer-Verlag.

Jao, D., Miller, S. D., and Venkatesan, R. (2009). Expander graphs based on grh with an application to elliptic curve cryptography. Journal of Number Theory, 129(5):1491–1504.

Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of Computation, 48(177):203–209.

Kohel, D. (1996). Endomorphism rings of elliptic curves over finite fields. PhD thesis, University of California at Berkley.

Miller, V. S. (1985). Use of elliptic curves in cryptography. In Advances in Cryptology - CRYPTO ’85, Santa Barbara, California, USA, August 18-22, 1985, Proceedings, pages 417–426.

Nilli, A. (1991). On the second eigenvalue of a graph. Discrete Math., 91(2):207–210.

Roetteler, M., Naehrig, M., Svore, K. M., and Lauter, K. (2017). Quantum resource estimates for computing elliptic curve discrete logarithms. In Proc. ASIACRYPT 2017, volume 10625, pages 241–270. Springer.

Rostovtsev, A. and Stolbunov, A. (2006). Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, Report 2006/145. [link].

Shor, P. W. (1995). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509.

Silverman, J. (1986). The Arithmetic of Elliptic Curves. Applications of Mathematics. Springer.

Stolbunov, A. (2010). Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 4(1930-5346):215.

Tani, S. (2009). Claw finding algorithms using quantum walk. Theoretical Computer Science, 410(50):5285 – 5297.

Tate, J. (1966). Endomorphisms of abelian varieties over finite fields. Invent. math., 2:134–144.

Vélu, J. (1971). Isogénies entre courbes elliptiques. C. R. Acad. Sci. Pars Sér. A-B, 273:A238–A241.

Washington, L. C. (2008). Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC.