nach oben

Journal of Cryptology

Erschienen in:

15.03.2016

Jacobian Coordinates on Genus 2 Curves

verfasst von: Huseyin Hisil, Craig Costello

Erschienen in: Journal of Cryptology | Ausgabe 2/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper presents a new projective coordinate system and new explicit algorithms which together boost the speed of arithmetic in the divisor class group of genus 2 curves. The proposed formulas generalize the use of Jacobian coordinates on elliptic curves, and their application improves the speed of performing cryptographic scalar multiplications in Jacobians of genus 2 curves over prime fields by an approximate factor of 1.25x. For example, on a single core of an Intel Core i7-3770 (Ivy Bridge), we show that replacing the previous best formulas with our new set improves the cost of generic scalar multiplications from 239,000 to 192,000 cycles and drops the cost of specialized GLV-style scalar multiplications from 155,000 to 123,000 cycles.

Vorheriger Artikel Photonic Side-Channel Analysis of Arbiter PUFs

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

For genus 2 scalar multiplications, it is usually advantageous to convert precomputed (lookup table) points to their affine representation using a shared inversion—see Sect. 8.2. This is why the double-and-add operations involve a “mixed” addition.

At least one exception here, as Gaudry points out, is the hashed version of ElGamal signatures [20, § 5.3].

Lubicz and Robert [31] have recently broken through the “full addition restriction” on Kummer varieties, but it is not yet clear how competitive their compatible addition formulas are in the context of raw scalar multiplications.

We adopted the notation \((q, r, s, t)\) over \((u_1,u_0,v_1,v_0)\) to avoid additional subscripts/superscripts when working with distinct elements in \(J_\mathcal {C}\). This eases the synchronization between, and readability of, the formulas in the paper and in our code.

In this case we will always write the last coordinate as \(W^2\) to illustrate the relationship between the last two coordinates. We subsequently note the difference between the computation of \(W^2\) and its use as a variable in the algorithm; for example, see steps 36 and 38 of Algorithm 1.

It is relatively straightforward to show that if \(J_\mathcal {C}\) has CM by \(\mathbb {Q}(\zeta _5)\) and full rational two-torsion, then either \(J_\mathcal {C}\) or \(J_{\mathcal {C}'}\) must contain a point of order 5; thus, the optimal cofactors are 16 and 80.

If the coefficient of \(x^3\) in \(\tilde{\mathcal {C}}\) was not a fourth power, one could still use this form of transformation to achieve another “small” coefficient, or in this case, work on the twist instead.

Our software has also been submitted to eBACS [6] to be benchmarked on a wider range of platforms.

The explicit algorithms exploiting these trade-offs are also provided in our online Magma code—see http://research.microsoft.com/en-us/downloads/37730278-3e37-47eb-91d1-cf889373677a/.

R. M. Avanzi, A note on the signed sliding window integer recoding and a left-to-right analogue, in H. Handschuh and M. A. Hasan, editors, Selected Areas in Cryptography, volume 3357 of Lecture Notes in Computer Science (Springer, 2004), pp. 130–143

R. Barbulescu, P. Gaudry, A. Joux, and E. Thomé. A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, in P. Q. Nguyen and E. Oswald, editors, EUROCRYPT, volume 8441 of Lecture Notes in Computer Science (Springer, 2014), pp. 1–16

D. J. Bernstein, C. Chuengsatiansup, T. Lange, and P. Schwabe. Kummer strikes back: New DH speed records., in P. Sarkar and T. Iwata, editors, Proceedings, Part I on Advances in Cryptology—ASIACRYPT 2014—20th International Conference on the Theory and Application of Cryptology and Information Security, 7–11 December, 2014, Kaoshiung, Taiwan, R.O.C., volume 8873 of Lecture Notes in Computer Science (Springer, 2014) pp. 317–337

D. J. Bernstein and T. Lange. Faster addition and doubling on elliptic curves, in ASIACRYPT 2007, volume 4833 of LNCS (Springer, 2007), pp. 29–50

D. J. Bernstein and T. Lange (2014). Explicit-formulas database, accessed 2 January 2014. http://www.hyperelliptic.org/EFD/

D. J. Bernstein and T. Lange. eBACS: ECRYPT Benchmarking of Cryptographic Systems, accessed 28 September, 2013. http://bench.cr.yp.to

G. Bisson, R. Cosset, and D. Robert. AVIsogenies—a library for computing isogenies between abelian varieties, November 2012. http://avisogenies.gforge.inria.fr

J. W. Bos, C. Costello, H. Hisil, and K. Lauter. Fast cryptography in genus 2, in T. Johansson and P. Q. Nguyen, editors, EUROCRYPT, volume 7881 of Lecture Notes in Computer Science (Springer, 2013), pp. 194–210. full version available at: http://eprint.iacr.org/2012/670

W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user language. J. Symb. Comput. 24(3–4), 235–265 (1997). [Computational algebra and number theory (London, 1993)]

10.

E. Brier and M. Joye. Weierstraß elliptic curves and side-channel attacks, in Public Key Cryptography (Springer, 2002), pp. 335–345

11.

D. V. Chudnovsky and G. V. Chudnovsky. Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Adv. Appl. Math. 7(4), 385–434 (1986)

12.

C. Costello and K. Lauter. Group law computations on Jacobians of hyperelliptic curves, in A. Miri and S. Vaudenay, editors, Selected Areas in Cryptography, volume 7118 of Lecture Notes in Computer Science (Springer, 2011), pp. 92–117

13.

O. Diao and M. Joye. Unified addition formulæ for hyperelliptic curve cryptosystems, in 3rd Workshop on Mathematical Cryptology (WMC 2012) and 3rd International Conference on Symbolic Computation and Cryptography (SCC 2012) (2012), pp. 45–50

14.

S. Erickson, T. Ho, and S. Zemedkun. Explicit projective formulas for real hyperelliptic curves of genus 2. Adv. Math. Commun. (2014) (To appear)

15.

X. Fan and G. Gong. Efficient explicit formulae for genus 2 hyperelliptic curves over prime fields and their implementations, in C. Adams, A. Miri, and M. Wiener, editors, Selected Areas in Cryptography, volume 4876 of Lecture Notes in Computer Science (Springer, Berlin, Heidelberg, 2007), pp. 155–172

16.

A. Faz-Hernández, P. Longa, and A. H. Sanchez. Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves, in J. Benaloh, editor, CT-RSA, volume 8366 of Lecture Notes in Computer Science (Springer, 2014), pp. 1–27

17.

S. D. Galbraith, M. Harrison, and D. J. Mireles Morales. Efficient hyperelliptic arithmetic using balanced representation for divisors, in A. J. van der Poorten and A. Stein, editors, ANTS, volume 5011 of Lecture Notes in Computer Science (Springer, 2008), pp. 342–356

18.

S. D. Galbraith, J. Pujolàs, C. Ritzenthaler, and B. A. Smith. Distortion maps for supersingular genus two curves. J. Math. Cryptol. 3(1), 1–18 (2009)

19.

R. P. Gallant, R. J. Lambert, and S. A. Vanstone. Faster point multiplication on elliptic curves with efficient endomorphisms, in J. Kilian, editor, CRYPTO, volume 2139 of Lecture Notes in Computer Science (Springer, 2001), pp. 190–200

20.

P. Gaudry. Fast genus 2 arithmetic based on Theta functions. J. Math. Cryptol. JMC 1(3), 243–265 (2007)

21.

P. Gaudry, D. R. Kohel, and B. A. Smith. Counting points on genus 2 curves with real multiplication, in D. H. Lee and X. Wang, editors, ASIACRYPT, volume 7073 of Lecture Notes in Computer Science (Springer, 2011), pp. 504–519

22.

P. Gaudry and E. Schost. Genus 2 point counting over prime fields. J. Symb. Comput. 47(4), 368–400 (2012)

23.

R. R. Goundar, M. Joye, A. Miyaji, M. Rivain, and A. Venelli. Scalar multiplication on Weierstraß elliptic curves from Co-Z arithmetic. J. Cryptogr. Eng. 1(2), 161–176 (2011)

24.

M. Hamburg. Fast and compact elliptic-curve cryptography. Cryptology ePrint Archive, Report 2012/309 (2012). http://eprint.iacr.org/

25.

H. Hisil. Elliptic curves, group law, and efficient computation. PhD thesis, Queensland University of Technology (2010)

26.

N. Koblitz. Elliptic curve cryptosystems. Math. Comput. 48(177), 203–209 (1987)

27.

N. Koblitz. Hyperelliptic cryptosystems. J. Cryptol. 1(3), 139–150 (1989)

28.

V. Kovtun and S. Kavun. Co-Z divisor addition formulae in Jacobian of genus 2 hyperelliptic curves over prime fields. Cryptology ePrint Archive, Report 2010/498 (2010). http://eprint.iacr.org/

29.

T. Lange. Formulae for arithmetic on genus 2 hyperelliptic curves. Appl. Algebra Eng. Commun. Comput. 15(5), 295–328 (2005)

30.

P. Longa and A. Miri. New composite operations and precomputation scheme for elliptic curve cryptosystems over prime fields, in R. Cramer, editor, Public Key Cryptography PKC 2008, volume 4939 of Lecture Notes in Computer Science (Springer, Berlin, Heidelberg, 2008), pp. 189–201

31.

D. Lubicz and D. Robert. A generalisation of Miller’s algorithm and applications to pairing computations on abelian varieties. Cryptology ePrint Archive, Report 2013/192 (2013). http://eprint.iacr.org/

32.

N. Meloni. New point addition formulae for ECC applications, in C. Carlet and B. Sunar, editors, WAIFI, volume 4547 of Lecture Notes in Computer Science (Springer, 2007), pp. 189–201

33.

V. S. Miller. Use of elliptic curves in cryptography, in H. C. Williams, editor, CRYPTO, volume 218 of Lecture Notes in Computer Science (Springer, 1985), pp. 417–426

34.

P. L. Montgomery. Speeding the Pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 243–264 (1987)

35.

A.-M. Spallek. Kurven vom geschlecht 2 und ihre anwendung in public-key-kryptosystemen. PhD thesis, Universität Essen. Institut für Experimentelle Mathematik (1994)

Titel: Jacobian Coordinates on Genus 2 Curves
verfasst von: Huseyin Hisil
Craig Costello
Publikationsdatum: 15.03.2016
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 2/2017
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-016-9227-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2017

Design Methodology and Validity Verification for a Reactive Countermeasure Against EM Attacks

Acoustic Cryptanalysis

Photonic Side-Channel Analysis of Arbiter PUFs

Efficient Cryptosystems From -th Power Residue Symbols

Secret-Sharing for NP

Security of Blind Signatures Revisited