doi: 10.3934/amc.2020048

Isogeny formulas for Jacobi intersection and twisted hessian curves

Institute of Computing, University of Campinas, Av. Albert Einstein 1251, Cidade Universitária "Zeferino Vaz", 13083-852, Campinas, SP, Brazil

Received  December 2018 Revised  December 2018 Published  November 2019

Fund Project: The first author is supported by Intel/FAPESP grant 14/50704-7 under project "Secure Execution of Cryptographic Algorithms"

The security of public-key systems is based on the difficulty of solving certain mathematical problems. With the possible emergence of large-scale quantum computers several of these problems, such as factoring and computing discrete logarithms, would be efficiently solved. Research on quantum-resistant public-key cryptography, also called post-quantum cryptography (PQC), has been productive in recent years. Public-key cryptosystems based on the problem of computing isogenies between supersingular elliptic curves appear to be good candidates for the next generation of public-key cryptography standards in the PQC scenario. In this work, motivated by a previous work by D. Moody and D. Shumow [17], we derived maps for elliptic curves represented in Jacobi Intersection and Twisted Hessian models. Our derivation follows a multiplicative strategy that contrasts with the additive idea presented in the Vélu formula. Finally, we present a comparison of computational cost to generate maps for isogenies of degree $ l $, where $ l = 2k + 1 $. In affine coordinates, our formulas require $ 46.8 \% $ less computation than the Huff model and $ 48\% $ less computation than the formulas given for the Extended Jacobi Quartic model when computing isogenies of degree $ 3 $. Considering higher degree isogenies as $ 101 $, our formulas require $ 23.4\% $ less computation than the Huff model and $ 24.7 \% $ less computation than the formula for the Extended Jacobi Quartic model.

Citation: João Paulo da Silva, Julio López, Ricardo Dahab. Isogeny formulas for Jacobi intersection and twisted hessian curves. Advances in Mathematics of Communications, doi: 10.3934/amc.2020048
References:
[1]

D. J. BernsteinP. BirknerM. JoyeT. Lange and C. Peters, Twisted Edwards curves, Progress in cryptology—AFRICACRYPT 2008, Lecture Notes in Comput. Sci., Springer, Berlin, 5023 (2008), 389-405.  doi: 10.1007/978-3-540-68164-9_26.  Google Scholar

[2]

D. J. Bernstein, C. Chuengsatiansup, D. Kohel and T. Lange, Twisted hessian curves, Progress in cryptology—LATINCRYPT 2015, Lecture Notes in Comput. Sci., Springer, Cham, 9230 (2015), 269–294, https://eprint.iacr.org/2015/781. doi: 10.1007/978-3-319-22174-8_15.  Google Scholar

[3]

D. Boneh and R. J. Lipton, Quantum cryptanalysis of hidden linear functions (extended abstract), Advances in Cryptology—CRYPTO '95 (Santa Barbara, CA, 1995), Lecture Notes in Comput. Sci., Springer, Berlin, 963 (1995), 424-437.  doi: 10.1007/3-540-44750-4_34.  Google Scholar

[4]

W. Castryck, T. Lange, C. Martindale, L. Panny and J. Renes, CSIDH: An efficient post-quantum commutative group action, Advances in cryptology—ASIACRYPT 2018. Part III, Lecture Notes in Comput. Sci., Springer, Cham, 11274 (2018), 395–427, https://eprint.iacr.org/2018/383.  Google Scholar

[5]

D. Charles, E. Goren and K. Lauter, Cryptographic hash functions from expander graphs, Journal of Cryptology, 22 (2009), 93–113, https://eprint.iacr.org/2006/021. doi: 10.1007/s00145-007-9002-x.  Google Scholar

[6]

L. Chen, D. Moody and Y.-K. Liu, National institute of standards and technology's post-quantum cryptography standardization, (2017). Google Scholar

[7]

A. ChildsD. Jao and V. Soukharev, Constructing elliptic curve isogenies in quantum subexponential time, Journal of Mathematical Cryptology, 8 (2014), 1-29.  doi: 10.1515/jmc-2012-0016.  Google Scholar

[8]

J.-M. Couveignes, Hard Homogeneous Spaces, Cryptology ePrint Archive, Report 2006/291, 2006, https://eprint.iacr.org/2006/291. Google Scholar

[9]

H. M. Edwards, A normal form for elliptic curves, Bull. Amer. Math. Soc. (N.S.), 44 (2007), 393-422.  doi: 10.1090/S0273-0979-07-01153-6.  Google Scholar

[10]

K. Eisentraeger, S. Hallgren and T. Morrison, On the Hardness of Computing Endomorphism Rings of Supersingular Elliptic Curves, Cryptology ePrint Archive, Report 2017/986, 2017, https://eprint.iacr.org/2017/986. Google Scholar

[11]

N. D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational Perspectives on Number Theory (Chicago, IL, 1995), AMS/IP Stud. Adv. Math., Amer. Math. Soc., Providence, RI, 7 (1998), 21-76.   Google Scholar

[12]

R. Q. Feng, M. L. Nie and H. F. Wu, Twisted Jacobi intersections curves, Theory and Applications of Models of Computation, Berlin, Heidelberg, Springer Berlin Heidelberg, (2010), 199–210. doi: 10.1007/978-3-642-13562-0_19.  Google Scholar

[13]

L. De Feo and D. Jao, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7071 (2011), 19-34.  doi: 10.1007/978-3-642-25405-5_2.  Google Scholar

[14]

D. Jao, R. Azarderakhs, M. Campagna, C. Costello, L. De Feo, B. Hess, A. Jalali, B. Koziel, B. LaMacchia, P. Longa, M. Naehrig, J. Renes, V. Soukharev and D. Urbanik, Supersingular isogeny key encapsulation, NIST Post-Quantum Cryptography Standardization, Round 1 Submission, (2017). Google Scholar

[15]

M. Joye and J.-J. Quisquater, Hessian elliptic curves and side-channel attacks, Cryptographic Hardware and Embedded Systems—CHES 2001 (Paris), Lecture Notes in Comput. Sci., Springer, Berlin, 2162 (2001), 402–410. doi: 10.1007/3-540-44709-1_33.  Google Scholar

[16]

M. Joye, M. Tibouchi and D. Vergnaud, Huff's model for elliptic curves, ANTS 2010: Algorithmic Number Theory, (2010), 234–250. doi: 10.1007/978-3-642-14518-6_20.  Google Scholar

[17]

D. Moody and D. Shumow, Analogues of Vélu's formulas for isogenies on alternate models of elliptic curves, Math. Comp., 85 (2016), 1929-1951.  doi: 10.1090/mcom/3036.  Google Scholar

[18]

A. Rostovtsev and A. Stolbunov, Public-key cryptosystem based on isogenies, Cryptology ePrint Archive, Report 2006/145, 2006, https://eprint.iacr.org/2006/145. Google Scholar

[19]

R. Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp., 44 (1985), 483-483.  doi: 10.2307/2007968.  Google Scholar

[20]

J. H. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, 106. Springer-Verlag, New York, 1986. doi: 10.1007/978-1-4757-1920-8.  Google Scholar

[21]

J. Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B, (273) (1972), A238–A241.  Google Scholar

[22]

L. C. Washington, Elliptic Curves: Number Theory and Cryptography, Second edition, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2008. doi: 10.1201/9781420071474.  Google Scholar

[23]

H. F. Wu and R. Q. Feng, Elliptic curves in Huff's model, Wuhan University Journal of Natural Sciences, 17 (2012), 473-480.  doi: 10.1007/s11859-012-0873-9.  Google Scholar

[24]

X. XuW. YuK. P. Wang and X. Y. He, Constructing isogenies on extended Jacobi quartic curves, Information Security and Cryptology, Lecture Notes in Comput. Sci., Springer, Cham, 10143 (2017), 416-427.   Google Scholar

show all references

References:
[1]

D. J. BernsteinP. BirknerM. JoyeT. Lange and C. Peters, Twisted Edwards curves, Progress in cryptology—AFRICACRYPT 2008, Lecture Notes in Comput. Sci., Springer, Berlin, 5023 (2008), 389-405.  doi: 10.1007/978-3-540-68164-9_26.  Google Scholar

[2]

D. J. Bernstein, C. Chuengsatiansup, D. Kohel and T. Lange, Twisted hessian curves, Progress in cryptology—LATINCRYPT 2015, Lecture Notes in Comput. Sci., Springer, Cham, 9230 (2015), 269–294, https://eprint.iacr.org/2015/781. doi: 10.1007/978-3-319-22174-8_15.  Google Scholar

[3]

D. Boneh and R. J. Lipton, Quantum cryptanalysis of hidden linear functions (extended abstract), Advances in Cryptology—CRYPTO '95 (Santa Barbara, CA, 1995), Lecture Notes in Comput. Sci., Springer, Berlin, 963 (1995), 424-437.  doi: 10.1007/3-540-44750-4_34.  Google Scholar

[4]

W. Castryck, T. Lange, C. Martindale, L. Panny and J. Renes, CSIDH: An efficient post-quantum commutative group action, Advances in cryptology—ASIACRYPT 2018. Part III, Lecture Notes in Comput. Sci., Springer, Cham, 11274 (2018), 395–427, https://eprint.iacr.org/2018/383.  Google Scholar

[5]

D. Charles, E. Goren and K. Lauter, Cryptographic hash functions from expander graphs, Journal of Cryptology, 22 (2009), 93–113, https://eprint.iacr.org/2006/021. doi: 10.1007/s00145-007-9002-x.  Google Scholar

[6]

L. Chen, D. Moody and Y.-K. Liu, National institute of standards and technology's post-quantum cryptography standardization, (2017). Google Scholar

[7]

A. ChildsD. Jao and V. Soukharev, Constructing elliptic curve isogenies in quantum subexponential time, Journal of Mathematical Cryptology, 8 (2014), 1-29.  doi: 10.1515/jmc-2012-0016.  Google Scholar

[8]

J.-M. Couveignes, Hard Homogeneous Spaces, Cryptology ePrint Archive, Report 2006/291, 2006, https://eprint.iacr.org/2006/291. Google Scholar

[9]

H. M. Edwards, A normal form for elliptic curves, Bull. Amer. Math. Soc. (N.S.), 44 (2007), 393-422.  doi: 10.1090/S0273-0979-07-01153-6.  Google Scholar

[10]

K. Eisentraeger, S. Hallgren and T. Morrison, On the Hardness of Computing Endomorphism Rings of Supersingular Elliptic Curves, Cryptology ePrint Archive, Report 2017/986, 2017, https://eprint.iacr.org/2017/986. Google Scholar

[11]

N. D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational Perspectives on Number Theory (Chicago, IL, 1995), AMS/IP Stud. Adv. Math., Amer. Math. Soc., Providence, RI, 7 (1998), 21-76.   Google Scholar

[12]

R. Q. Feng, M. L. Nie and H. F. Wu, Twisted Jacobi intersections curves, Theory and Applications of Models of Computation, Berlin, Heidelberg, Springer Berlin Heidelberg, (2010), 199–210. doi: 10.1007/978-3-642-13562-0_19.  Google Scholar

[13]

L. De Feo and D. Jao, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Post-Quantum Cryptography, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7071 (2011), 19-34.  doi: 10.1007/978-3-642-25405-5_2.  Google Scholar

[14]

D. Jao, R. Azarderakhs, M. Campagna, C. Costello, L. De Feo, B. Hess, A. Jalali, B. Koziel, B. LaMacchia, P. Longa, M. Naehrig, J. Renes, V. Soukharev and D. Urbanik, Supersingular isogeny key encapsulation, NIST Post-Quantum Cryptography Standardization, Round 1 Submission, (2017). Google Scholar

[15]

M. Joye and J.-J. Quisquater, Hessian elliptic curves and side-channel attacks, Cryptographic Hardware and Embedded Systems—CHES 2001 (Paris), Lecture Notes in Comput. Sci., Springer, Berlin, 2162 (2001), 402–410. doi: 10.1007/3-540-44709-1_33.  Google Scholar

[16]

M. Joye, M. Tibouchi and D. Vergnaud, Huff's model for elliptic curves, ANTS 2010: Algorithmic Number Theory, (2010), 234–250. doi: 10.1007/978-3-642-14518-6_20.  Google Scholar

[17]

D. Moody and D. Shumow, Analogues of Vélu's formulas for isogenies on alternate models of elliptic curves, Math. Comp., 85 (2016), 1929-1951.  doi: 10.1090/mcom/3036.  Google Scholar

[18]

A. Rostovtsev and A. Stolbunov, Public-key cryptosystem based on isogenies, Cryptology ePrint Archive, Report 2006/145, 2006, https://eprint.iacr.org/2006/145. Google Scholar

[19]

R. Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp., 44 (1985), 483-483.  doi: 10.2307/2007968.  Google Scholar

[20]

J. H. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, 106. Springer-Verlag, New York, 1986. doi: 10.1007/978-1-4757-1920-8.  Google Scholar

[21]

J. Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B, (273) (1972), A238–A241.  Google Scholar

[22]

L. C. Washington, Elliptic Curves: Number Theory and Cryptography, Second edition, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2008. doi: 10.1201/9781420071474.  Google Scholar

[23]

H. F. Wu and R. Q. Feng, Elliptic curves in Huff's model, Wuhan University Journal of Natural Sciences, 17 (2012), 473-480.  doi: 10.1007/s11859-012-0873-9.  Google Scholar

[24]

X. XuW. YuK. P. Wang and X. Y. He, Constructing isogenies on extended Jacobi quartic curves, Information Security and Cryptology, Lecture Notes in Comput. Sci., Springer, Cham, 10143 (2017), 416-427.   Google Scholar

Table 1.  Operation Counting for Isogenies Evaluation in Alternative Models in affine coordinates
MODEL OPERATION COST
Edwards [17] $ (3k+1)M+2S+3kC+I $
Huff [17] $ (4k-2)M+2S+2kC+2I $
Ext. Jacobi Quartic [24] $ (4k+2)M+3S+(7k+4)C+2I $
Weierstrass [17] $ (3+o(1))(2k+1)M+S+(3+o(1))(2k+1)C+I $ 1
Intersec. de Jacobi $ (4k+2)M+3S+(5k+1)C+I $
Twisted Hessian $ (5k+2)M+3S+(9k)C+I $
MODEL OPERATION COST
Edwards [17] $ (3k+1)M+2S+3kC+I $
Huff [17] $ (4k-2)M+2S+2kC+2I $
Ext. Jacobi Quartic [24] $ (4k+2)M+3S+(7k+4)C+2I $
Weierstrass [17] $ (3+o(1))(2k+1)M+S+(3+o(1))(2k+1)C+I $ 1
Intersec. de Jacobi $ (4k+2)M+3S+(5k+1)C+I $
Twisted Hessian $ (5k+2)M+3S+(9k)C+I $
Table 2.  Operations Counting for Evaluation of Isogenies in Alternative Models, given in affine coordinates, as a function of the number of multiplications in the base field
MODEL OPERATION COST
$I=100M$,
$S=1M$,
$*const=0M$
$I=100M$,
$S=0, 8M$,
$*const=0M$
$I=100M$
$S=0, 67M$,
$*const=0M$
Edwards [17] $(3k+103)M$ $(3k+102.6)M$ $(3k+102.34)M$
Huff [17] $(4k+200)M$ $(4k+199.6)M$ $(4k+199.34)M$
Ext. Jacobi Quartic [24] $(4k+205)M$ $(4k+204.4)M$ $(4k+204.01)M$
Weierstrass [17] - - -
Jacobi Intersection $(4k+105)M$ $(4k+104.4)M$ $(4k+104.01)M$
Twisted Hessian $(5k+105)M$ $(5k+104.4)M$ $(5k+104.01)M$
MODEL OPERATION COST
$I=100M$,
$S=1M$,
$*const=0M$
$I=100M$,
$S=0, 8M$,
$*const=0M$
$I=100M$
$S=0, 67M$,
$*const=0M$
Edwards [17] $(3k+103)M$ $(3k+102.6)M$ $(3k+102.34)M$
Huff [17] $(4k+200)M$ $(4k+199.6)M$ $(4k+199.34)M$
Ext. Jacobi Quartic [24] $(4k+205)M$ $(4k+204.4)M$ $(4k+204.01)M$
Weierstrass [17] - - -
Jacobi Intersection $(4k+105)M$ $(4k+104.4)M$ $(4k+104.01)M$
Twisted Hessian $(5k+105)M$ $(5k+104.4)M$ $(5k+104.01)M$
Table 3.  Operations Counting for Isogenies Evaluation in Alternative Models using Projective Coordinates
MODEL OPERATION COST
Edwards [17] $ (3k+3)M+4S+3kC $
Huff [17] $ (4k+3)M+3S+4kC $
Ext. Jacobi Quartic [24] -
Weierstrass [17] -
Jacobi Intersection $ (4k+7)M+5S+(6k+2)C $
Twisted Hessian $ (5k+2)M+3S+(9k)C $
MODEL OPERATION COST
Edwards [17] $ (3k+3)M+4S+3kC $
Huff [17] $ (4k+3)M+3S+4kC $
Ext. Jacobi Quartic [24] -
Weierstrass [17] -
Jacobi Intersection $ (4k+7)M+5S+(6k+2)C $
Twisted Hessian $ (5k+2)M+3S+(9k)C $
Table 4.  Operations Counting for Isogeny Evaluation on Alternative Models, using projective coordinates, as a function of the number of multiplications in the base field
MODEL OPERATION COST
$S=1M$,
$*const=0M$
$S=0, 8M$,
$*const=0M$
$S=0, 67M$,
$*const=0M$
Edwards [17] $(3k+7)M$ $(3k+6.2)M$ $(3k+5.68)M$
Huff [17] $(4k+6)M$ $(4k+5.4)M$ $(4k+5.01)M$
Ext. Jacobi Quartic [24] - - -
Weierstrass [17] - - -
Jacobi Intersection $(4k+12)M$ $(4k+11)M$ $(4k+10.35)M$
Twisted Hessian $(5k+5)M$ $(5k+4.4)M$ $(5k+4, 01)M$
MODEL OPERATION COST
$S=1M$,
$*const=0M$
$S=0, 8M$,
$*const=0M$
$S=0, 67M$,
$*const=0M$
Edwards [17] $(3k+7)M$ $(3k+6.2)M$ $(3k+5.68)M$
Huff [17] $(4k+6)M$ $(4k+5.4)M$ $(4k+5.01)M$
Ext. Jacobi Quartic [24] - - -
Weierstrass [17] - - -
Jacobi Intersection $(4k+12)M$ $(4k+11)M$ $(4k+10.35)M$
Twisted Hessian $(5k+5)M$ $(5k+4.4)M$ $(5k+4, 01)M$
[1]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281

[2]

Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489

[3]

Wenxue Huang, Yuanyi Pan, Lihong Zheng. Proportional association based roi model. Big Data & Information Analytics, 2017, 2 (2) : 119-125. doi: 10.3934/bdia.2017004

[4]

Hayden Schaeffer, John Garnett, Luminita A. Vese. A texture model based on a concentration of measure. Inverse Problems & Imaging, 2013, 7 (3) : 927-946. doi: 10.3934/ipi.2013.7.927

[5]

Michele L. Joyner, Cammey C. Manning, Whitney Forbes, Michelle Maiden, Ariel N. Nikas. A physiologically-based pharmacokinetic model for the antibiotic ertapenem. Mathematical Biosciences & Engineering, 2016, 13 (1) : 119-133. doi: 10.3934/mbe.2016.13.119

[6]

Elena Rossi. A justification of a LWR model based on a follow the leader description. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 579-591. doi: 10.3934/dcdss.2014.7.579

[7]

Dieter Armbruster, Christian Ringhofer, Andrea Thatcher. A kinetic model for an agent based market simulation. Networks & Heterogeneous Media, 2015, 10 (3) : 527-542. doi: 10.3934/nhm.2015.10.527

[8]

Monique Chyba, Aaron Tamura-Sato. Morphogenesis modelization of a fractone-based model. Discrete & Continuous Dynamical Systems - B, 2017, 22 (1) : 29-58. doi: 10.3934/dcdsb.2017002

[9]

Zhiyong Sun, Toshiharu Sugie. Identification of Hessian matrix in distributed gradient-based multi-agent coordination control systems. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 297-318. doi: 10.3934/naco.2019020

[10]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237

[11]

Jianping Zhang, Ke Chen, Bo Yu, Derek A. Gould. A local information based variational model for selective image segmentation. Inverse Problems & Imaging, 2014, 8 (1) : 293-320. doi: 10.3934/ipi.2014.8.293

[12]

David Rossmanith, Ashok Puri. Recasting a Brinkman-based acoustic model as the damped Burgers equation. Evolution Equations & Control Theory, 2016, 5 (3) : 463-474. doi: 10.3934/eect.2016014

[13]

Seunghee Lee, Ganguk Hwang. A new analytical model for optimized cognitive radio networks based on stochastic geometry. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1883-1899. doi: 10.3934/jimo.2017023

[14]

Holly Gaff. Preliminary analysis of an agent-based model for a tick-borne disease. Mathematical Biosciences & Engineering, 2011, 8 (2) : 463-473. doi: 10.3934/mbe.2011.8.463

[15]

Zizi Wang, Zhiming Guo, Huaqin Peng. Dynamical behavior of a new oncolytic virotherapy model based on gene variation. Discrete & Continuous Dynamical Systems - S, 2017, 10 (5) : 1079-1093. doi: 10.3934/dcdss.2017058

[16]

J. Ignacio Tello. On a mathematical model of tumor growth based on cancer stem cells. Mathematical Biosciences & Engineering, 2013, 10 (1) : 263-278. doi: 10.3934/mbe.2013.10.263

[17]

Eleonora Messina. Numerical simulation of a SIS epidemic model based on a nonlinear Volterra integral equation. Conference Publications, 2015, 2015 (special) : 826-834. doi: 10.3934/proc.2015.0826

[18]

Junyoung Jang, Kihoon Jang, Hee-Dae Kwon, Jeehyun Lee. Feedback control of an HBV model based on ensemble kalman filter and differential evolution. Mathematical Biosciences & Engineering, 2018, 15 (3) : 667-691. doi: 10.3934/mbe.2018030

[19]

Yangang Chen, Justin W. L. Wan. Numerical method for image registration model based on optimal mass transport. Inverse Problems & Imaging, 2018, 12 (2) : 401-432. doi: 10.3934/ipi.2018018

[20]

Mengshi Shu, Rui Fu, Wendi Wang. A bacteriophage model based on CRISPR/Cas immune system in a chemostat. Mathematical Biosciences & Engineering, 2017, 14 (5&6) : 1361-1377. doi: 10.3934/mbe.2017070

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (37)
  • HTML views (27)
  • Cited by (0)

[Back to Top]