Arithmetic using compression on elliptic curves in Huff's form and its applications

Authors

Abstract

In this paper for elliptic curves provided by Huff's equation $H_{a,b}: ax(y^2-1) = by(x^2-1)$ and general Huff's equation $G_{\overline{a},\overline{b}}\ :\ {\overline{x}}(\overline{a}{\overline{y}}^2-1)={\overline{y}}(\overline{b}{\overline{x}}^2-1)$ and degree 2 compression function $f(x,y) = xy$ on these curves, herein we provide formulas for doubling and differential addition after compression, which for Huff's curves are as efficient as Montgomery's formulas for Montgomery's curves $By^2 = x^3 + Ax^2 + x$. For these curves we also provided point recovery formulas after compression, which for
a point $P$ on these curves allows to compute $[n]f(P)$ after compression using the Montgomery ladder algorithm, and then recover $[n]P$. Using formulas of Moody and Shumow for computing odd degree isogenies on general Huff's curves, we have also provide formulas for computing odd degree isogenies after compression for these curves.
Moreover, it is shown herein how to apply obtained formulas using compression to the ECM algorithm. In the appendix, we present examples of Huff's curves convenient for the isogeny-based cryptography, where compression can be used.

References

@article{bernstein2017montgomery,

title={Montgomery curves and the Montgomery ladder.},

author={Bernstein, Daniel J and Lange, Tanja},

journal={IACR Cryptol. ePrint Arch.},

volume={2017},

pages={293},

year={2017}

}

@article{costello2018montgomery,

title={Montgomery curves and their arithmetic},

author={Costello, Craig and Smith, Benjamin},

journal={Journal of Cryptographic Engineering},

volume={8},

number={3},

pages={227--240},

year={2018},

doi = {10.1007/s13389-017-0157-6},

publisher={Springer}

}

@article{Montgomery1987SpeedingTP,

title={Speeding the Pollard and elliptic curve methods of factorization},

author={Peter L. Montgomery},

journal={Mathematics of Computation},

year={1987},

volume={48},

pages={243-264},

doi = {10.1090/S0025-5718-1987-0866113-7}

}

@inproceedings{brier2002weierstrass,

title={Weierstra{ss} elliptic curves and side-channel attacks},

author={Brier, Eric and Joye, Marc},

booktitle={International workshop on public key cryptography},

pages={335--345},

year={2002},

doi = {10.1007/3-540-45664-3_24},

organization={Springer}

}

@inproceedings{farashahi2017differential,

title={Differential addition on twisted Edwards curves},

author={Farashahi, Reza Rezaeian and Hosseini, Seyed Gholamhossein},

booktitle={Australasian Conference on Information Security and Privacy},

pages={366--378},

year={2017},

doi = {10.1007/978-3-319-59870-3_21},

organization={Springer}

}

@inproceedings{justus2010differential,

title={Differential addition in generalized Edwards coordinates},

author={Justus, Benjamin and Loebenberger, Daniel},

booktitle={International Workshop on Security},

pages={316--325},

year={2010},

doi = {10.1007/978-3-642-16825-3_21},

organization={Springer}

}

@inproceedings{farashahi2010efficient,

title={Efficient arithmetic on Hessian curves},

author={Farashahi, Reza R and Joye, Marc},

booktitle={International Workshop on Public Key Cryptography},

pages={243--260},

year={2010},

doi = {10.1007/978-3-642-13013-7_15},

organization={Springer}

}

@article{castryck2011toric,

title={Toric forms of elliptic curves and their arithmetic},

author={Castryck, Wouter and Vercauteren, Frederik},

journal={Journal of Symbolic Computation},

volume={46},

number={8},

pages={943--966},

year={2011},

doi = {10.1016/j.jsc.2011.02.003},

publisher={Elsevier}

}

@article{drylo2019determining,

title={Determining Formulas Related to Point Compression on Alternative Models of Elliptic Curves},

author={Dry{l}o, Robert and Kijko, Tomasz and Wro{'n}ski, Micha{l}},

journal={Fundamenta Informaticae},

volume={169},

number={4},

pages={285--294},

year={2019},

doi = {10.3233/FI-2019-1848},

publisher={IOS Press}

}

@inproceedings{okeya2001efficient,

title={Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery-form elliptic curve},

author={Okeya, Katsuyuki and Sakurai, Kouichi},

booktitle={International Workshop on Cryptographic Hardware and Embedded Systems},

pages={126--141},

year={2001},

doi = {10.1007/3-540-44709-1_12},

organization={Springer}

}

@inproceedings{joye2010huff,

title={Huff’s model for elliptic curves},

author={Joye, Marc and Tibouchi, Mehdi and Vergnaud, Damien},

booktitle={International Algorithmic Number Theory Symposium},

pages={234--250},

year={2010},

doi = {10.1007/978-3-642-14518-6_20},

organization={Springer}

}

@article{wu2012elliptic,

title={Elliptic curves in Huff’s model},

author={Wu, Hongfeng and Feng, Rongquan},

journal={Wuhan University Journal of Natural Sciences},

volume={17},

number={6},

pages={473--480},

year={2012},

doi = {10.1007/s11859-012-0873-9},

publisher={Springer}

}

@inproceedings{oliveira2017pre,

title={How to (pre-) compute a ladder},

author={Oliveira, Thomaz and L{'o}pez, Julio and H{i}{c{s}}{i}l, H{"u}seyin and Faz-Hern{'a}ndez, Armando and Rodr{'i}guez-Henr{'i}quez, Francisco},

booktitle={International Conference on Selected Areas in Cryptography},

pages={172--191},

year={2017},

doi = {10.1007/978-3-319-72565-9_9},

organization={Springer}

}

@inproceedings{farashahi2016differential,

title={Differential addition on binary elliptic curves},

author={Farashahi, Reza Rezaeian and Hosseini, Seyed Gholamhossein},

booktitle={International Workshop on the Arithmetic of Finite Fields},

pages={21--35},

year={2016},

doi = {10.1007/978-3-319-55227-9_2},

organization={Springer}

}

@article{moody2016analogues,

title={Analogues of V{'e}lu’s formulas for isogenies on alternate models of elliptic curves},

author={Moody, Dustin and Shumow, Daniel},

journal={Mathematics of Computation},

volume={85},

number={300},

pages={1929--1951},

doi = {10.1090/mcom/3036},

year={2016}

}

@inproceedings{costello2017simple,

title={A simple and compact algorithm for SIDH with arbitrary degree isogenies},

author={Costello, Craig and Hisil, Huseyin},

booktitle={International Conference on the Theory and Application of Cryptology and Information Security},

pages={303--329},

year={2017},

doi = {10.1007/978-3-319-70697-9_11},

organization={Springer}

}

@techreport{key,

author = {Jao, David},

title = {Supersingular Isogeny Key Encapsulation},

institution = {},

year = {2020}

}

@unknown{jao2019supersingular,

author = {Jao, David and Azarderakhsh, Reza and Campagna, Matthew and Costello, Craig and Feo, Luca and Hess, Basil and Jalali, Amir and Koziel, Brian and LaMacchia, Brian and Longa, Patrick and Naehrig, Michael and Pereira, Geovandro and Renes, Joost and Soukharev, Vladimir and Urbanik, David},

year = {2019},

month = {04},

pages = {},

title = {Supersingular Isogeny Key Encapsulation},

}

@article{jeon2011families,

title={Families of elliptic curves over quartic number fields with prescribed torsion subgroups},

author={Jeon, Daeyeol and Kim, Chang Heon and Lee, Yoonjin},

journal={Mathematics of computation},

volume={80},

number={276},

pages={2395--2410},

doi = {10.1090/S0025-5718-2011-02493-2},

year={2011}

}

Downloads

Published

2024-04-19

Issue

Section

Cryptography and Cybersecurity