• Previous Article
    The weight distribution of families of reducible cyclic codes through the weight distribution of some irreducible cyclic codes
  • AMC Home
  • This Issue
  • Next Article
    Challenge codes for physically unclonable functions with Gaussian delays: A maximum entropy problem
August  2020, 14(3): 507-523. 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  August 2020 Early access  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, 2020, 14 (3) : 507-523. 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.

[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.

[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.

[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.

[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.

[6]

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

[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.

[8]

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

[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.

[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.

[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. 

[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.

[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.

[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).

[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.

[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.

[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.

[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.

[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.

[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.

[21]

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

[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.

[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.

[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. 

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.

[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.

[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.

[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.

[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.

[6]

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

[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.

[8]

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

[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.

[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.

[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. 

[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.

[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.

[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).

[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.

[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.

[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.

[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.

[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.

[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.

[21]

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

[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.

[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.

[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. 

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]

Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022031

[2]

Wissam Ghantous. Loops, multi-edges and collisions in supersingular isogeny graphs. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022038

[3]

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

[4]

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

[5]

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

[6]

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

[7]

Xuhui Wang, Lei Hu. A new method to solve the Hamilton-Jacobi-Bellman equation for a stochastic portfolio optimization model with boundary memory. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021137

[8]

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

[9]

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

[10]

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

[11]

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

[12]

Matteo Ludovico Bedini, Rainer Buckdahn, Hans-Jürgen Engelbert. On the compensator of the default process in an information-based model. Probability, Uncertainty and Quantitative Risk, 2017, 2 (0) : 10-. doi: 10.1186/s41546-017-0017-4

[13]

Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantum-safe identity-based broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022026

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Wenjia Jing, Olivier Pinaud. A backscattering model based on corrector theory of homogenization for the random Helmholtz equation. Discrete and Continuous Dynamical Systems - B, 2019, 24 (10) : 5377-5407. doi: 10.3934/dcdsb.2019063

[19]

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

[20]

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

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (636)
  • HTML views (466)
  • Cited by (0)

[Back to Top]