Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Cryptology
Published in: Journal of Cryptology 3/2019

25-04-2018

Koblitz Curves over Quadratic Fields

Authors: Thomaz Oliveira, Julio López, Daniel Cervantes-Vázquez, Francisco Rodríguez-Henríquez

Published in: Journal of Cryptology | Issue 3/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this work, we retake an old idea that Koblitz presented in his landmark paper (Koblitz, in: Proceedings of CRYPTO 1991. LNCS, vol 576, Springer, Berlin, pp 279–287, 1991), where he suggested the possibility of defining anomalous elliptic curves over the base field \({\mathbb {F}}_4\). We present a careful implementation of the base and quadratic field arithmetic required for computing the scalar multiplication operation in such curves. We also introduce two ordinary Koblitz-like elliptic curves defined over \({\mathbb {F}}_4\) that are equipped with efficient endomorphisms. To the best of our knowledge, these endomorphisms have not been reported before. In order to achieve a fast reduction procedure, we adopted a redundant trinomial strategy that embeds elements of the field \({\mathbb {F}}_{4^{m}},\) with m a prime number, into a ring of higher order defined by an almost irreducible trinomial. We also suggest a number of techniques that allow us to take full advantage of the native vector instructions of high-end microprocessors. Our software library achieves the fastest timings reported for the computation of the timing-protected scalar multiplication on Koblitz curves, and competitive timings with respect to the speed records established recently in the computation of the scalar multiplication over binary and prime fields.
previous article The Magic of ELFs
next article Beyond Conventional Security in Sponge-Based Authenticated Encryption Modes

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Footnotes
1
See [54] for a historical recount of the first three decades of elliptic curve cryptography.
 
2
Building on the work by Blake et al. [16].
 
3
Sometimes also called Semaev’s polynomials.
 
4
It is interesting to note that Semaev’s original work in [79] described an attack that in principle can be applied not only to binary but to all elliptic curves [75].
 
5
Nevertheless, the influential French Agence Nationale de la Sécurité des Systèmes d’Information (ANSSI) considers in [2] that in terms of their security, “Les courbes elliptiques définies sur GF(p) ne sont pas différenciées de celles définies sur \(GF(2^n)\)” (elliptic curves defined over GF(p) should not be differentiated from those defined over \(GF(2^n)\)).
 
6
Another problem may occur if the genus of C is too small. For example, the Jacobian of a curve C in \({\mathbb {F}}_2\) would be too small to give any useful information about the DLP over \(E({\mathbb {F}}_{2^m})\) [57].
 
7
Usually the order p is composite. Also, every prime factor of p is smaller than r (see Table 1).
 
8
We are considering only positive digits, since the cost of computing the negative points in binary elliptic curves is negligible.
 
9
While this is undoubtedly not the optimal approach for computing these values, the point pre-computation represents only a tiny fraction of the whole scalar multiplication performance cost.
 
10
Full addition is the operation of adding two points both represented in projective coordinates, whereas a mixed addition is the operation of adding one point represented in projective coordinates with another represented in affine coordinates. Note that a full addition is always more costly than a mixed addition.
 
11
Notice that the multiples \(\alpha _v P\) as shown in Table 2 must be computed out of order. The order for computing the multiples is shown in roman numbers.
 
12
For a more detailed explanation of the shift-and-add and the mul-and-add reduction methods for binary fields, see [18].
 
13
In this document, we represent a 128-bit register R with its most (M) and least (L) significant packed 64-bit words as \(R = M|L\).
 
14
On recent Intel architectures, this instruction is denominated pshufd [43].
 
15
For the sake of simplicity, we will not differentiate the endomorphisms \(\tau \) and \(\bar{\tau }\) when describing the \(\tau \)-and-add algorithms.
 
16
Except for aggressive choices for the parameter w (usually in the fixed-point scenario), computing the \(\tau \) endomorphism with lookup tables is not worthwhile in modern platforms. This is because performing the field squaring through carry-less instructions costs approximately five times the cost of computing a multi-squaring operation via pre-computed values.
 
17
In the \(\tau \)-and-add algorithms, the \(\lambda \)-doubling and the \(\lambda \)-full addition formulas are only used in the pre- and post-computation phases.
 
Literature
1.
2.
3.
D.F. Aranha, A. Faz-Hernández, J. López, F. Rodríguez-Henríquez, Faster implementation of scalar multiplication on Koblitz curves, in Proceedings of LATINCRYPT 2012. LNCS, vol. 7533 (Springer, Berlin, 2012), pp. 177–193
4.
D.F. Aranha, J.López, D. Hankerson, Efficient software implementation of binary field arithmetic using vector instruction sets, in Proceedings of LATINCRYPT 2010. LNCS, vol. 6212 (Springer, Berlin, 2010), pp. 144–161
5.
A.U. Ay, E. Öztürk, F. Rodríguez-Henríquez, E. Savaş, Design and implementation of a constant-time FPGA accelerator for fast elliptic curve cryptography, in ReConFig 2016 (IEEE, Piscataway, 2016), pp. 1–8
6.
R. Barbulescu, P. Gaudry, A. Joux, E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, in Proceedings of EUROCRYPT 2014. LNCS, vol. 8441 (Springer, Berlin, 2014), pp. 1–16
7.
P. Belgarric, P.-A. Fouque, G. Macario-Rat, M. Tibouchi, Side-channel analysis of Weierstrass and Koblitz curve ECDSA on Android smartphones, in Proceedings of CT-RSA 2016. LNCS, vol. 9610 (Springer, Berlin, 2016), pp. 236–252
8.
D.J. Bernstein, C. Chuengsatiansup, T. Lange, P. Schwabe, Kummer strikes back: new DH speed records, in Proceedings of ASIACRYPT 2014. LNCS, vol. 8873 (Springer, Berlin, 2014), pp. 317–337
9.
10.
11.
12.
13.
J. Beuchat, N. Brisebarre, J. Detrey, E. Okamoto, F. Rodríguez-Henríquez, A comparison between hardware accelerators for the modified Tate pairing over \({{\mathbb{F}}}_{2^m}\) and \({\mathbb{F}}_{3^m}\), in Proceedings of Pairing 2008. LNCS, vol. 5209 (Springer, Berlin, 2008), pp. 297–315
14.
J. Beuchat, J. Detrey, N. Estibals, E. Okamoto, F. Rodríguez-Henríquez, Fast architectures for the \(\eta _{T}\) pairing over small-characteristic supersingular elliptic curves. IEEE Trans. Comput. 60(2), 266–281 (2011)MathSciNetCrossRefMATH
15.
J. Beuchat, E. López-Trejo, L. Martínez-Ramos, S. Mitsunari, F. Rodríguez-Henríquez, Multi-core implementation of the Tate pairing over supersingular elliptic curves, in Proceedings of CANS 2009. LNCS, vol. 5888 (Springer, Berlin, 2009), pp. 413–432
16.
I.F. Blake, R. Fuji-Hara, R.C. Mullin, S.A. Vanstone, Computing logarithms in finite fields of characteristic two. SIAM J. Algebr. Discrete Methods 5, 276–285 (1984)MathSciNetCrossRefMATH
17.
18.
M. Bluhm, S. Gueron, Fast software implementation of binary elliptic curve cryptography. J. Cryptogr. Eng. 5(3), 215–226 (2015)CrossRef
19.
D. Boneh, M.K. Franklin, Identity-based encryption from the Weil pairing, in Proceedings of CRYPTO 2001. LNCS, vol. 2139 (Springer, Berlin, 2001), pp. 213–229
20.
J.W. Bos, C. Costello, P. Longa, M. Naehrig, Selecting elliptic curves for cryptography: an efficiency and security analysis. J. Cryptogr. Eng. 6(4), 259–286 (2016)CrossRef
21.
R.P. Brent, P. Zimmermann, Algorithms for finding almost irreducible and almost primitive trinomials, in Primes and Misdemeanours: Lectures in Honour of the Sixtieth Birthday of Hugh Cowie Williams (Fields Institute, Toronto, 2003), p. 212
22.
23.
24.
C. Costello, P. Longa, Four\(({\mathbb{Q}}\)): four-dimensional decompositions on a \(({\mathbb{Q}}\))-curve over the Mersenne prime, in Proceedings of ASIACRYPT 2015. LNCS, vol. 9452 (Springer, Berlin, 2015), pp. 214–235
25.
26.
C. Doche, Redundant trinomials for finite fields of characteristic 2, in Proceedings of ACISP 2005. LNCS, vol. 3574 (Springer, Berlin, 2005), pp. 122–133
27.
28.
29.
J. Faugère, L. Perret, C. Petit, G. Renault. Improving the complexity of index calculus algorithms in elliptic curves over binary fields, in Proceedings of EUROCRYPT 2012. LNCS, vol. 7237 (Springer, Berlin 2012), pp. 27–44
30.
S.D. Galbraith, P. Gaudry, Recent progress on the elliptic curve discrete logarithm problem. Des. Codes Cryptogr. 78(1), 51–72 (2016)MathSciNetCrossRefMATH
31.
S.D. Galbraith, S.W. Gebregiyorgis, Summation polynomial algorithms for elliptic curves in characteristic two, in Proceedings of INDOCRYPT 2014. LNCS, vol. 8885 (Springer, Berlin, 2014), pp. 409–427
32.
S.D. Galbraith, X. Lin, M. Scott, Endomorphisms for faster elliptic curve cryptography on a large class of curves, in Proceedings of EUROCRYPT 2009. LNCS, vol. 5479 (Springer, Berlin, 2009), pp. 518–535
33.
S.D. Galbraith, N.P. Smart, A cryptographic application of Weil descent, in Proceedings of Cryptography and Coding. LNCS, vol. 1746 (Springer, Berlin, 1999), pp. 191–200
34.
R.P. Gallant, R.J. Lambert, S.A. Vanstone, Improving the parallelized pollard lambda search on anomalous binary curves. Math. Comput. 69(232), 1699–1705 (2000)MathSciNetCrossRefMATH
35.
P. Gaudry, Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. J. Symb. Comput. 44(12), 1690–1702 (2009)MathSciNetCrossRefMATH
36.
P. Gaudry, F. Hess, N.P. Smart, Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptol. 15, 19–46 (2002)MathSciNetCrossRefMATH
37.
D. Genkin, L. Valenta, Y. Yarom, May the fourth be with you: a microarchitectural side channel attack on several real-world applications of curve25519. Cryptology ePrint Archive, Report 2017/806 (2017). https://​eprint.​iacr.​org/​2017/​806
38.
39.
D. Hankerson, K. Karabina, A. Menezes, Analyzing the Galbraith–Lin–Scott point multiplication method for elliptic curves over binary fields. IEEE Trans. Comput. 58(10), 1411–1420 (2009)MathSciNetCrossRefMATH
40.
D. Hankerson, A.J. Menezes, S. Vanstone, Guide to Elliptic Curve Cryptography (Springer, Secaucus, 2003)MATH
41.
42.
43.
Intel Corporation, Intel 64 and IA-32 architectures software developers manual, 253665-064US (2017)
44.
T. Itoh, S. Tsujii, A fast algorithm for computing multiplicative inverses in GF\((2^m)\) using normal bases. Inf. Comput. 78(3), 171–177 (1988)CrossRefMATH
45.
A. Joux, A one round protocol for tripartite Diffie–Hellman, in Proceedings of ANTS-IV. LNCS, vol. 1838 (Springer, Berlin, 2000), pp. 385–394
46.
47.
A. Joux, A new index calculus algorithm with complexity \(L(1/4+o(1))\) in small characteristic, in Proceedings of SAC 2013. LNCS, vol. 8282 (Springer, Berlin, 2014), pp. 355–379
48.
M. Joye, M. Tunstall, Exponent recoding and regular exponentiation algorithms, in AFRICACRYPT 2009. LNCS, vol. 5580 (Springer, Berlin, 2009), pp. 334–349
49.
50.
E. Knudsen, Elliptic scalar multiplication using point halving, in Proceedings of ASIACRYPT 99. LNCS, vol. 1716 (Springer, Berlin, 1999), pp. 135–149
51.
52.
N. Koblitz, Constructing elliptic curve cryptosystems in characteristic 2, in Proceedings of CRYPTO 90. LNCS, vol. 537 (1990), pp. 156–167
53.
N. Koblitz, CM-curves with good cryptographic properties, in Proceedings of CRYPTO 1991. LNCS, vol. 576 (Springer, Berlin, 1991), pp. 279–287
54.
55.
P.C. Kocher, J. Jaffe, B. Jun, Differential power analysis, in Proceedings of CRYPTO 99. LNCS, vol. 1666 (Springer, Berlin, 1999), pp. 388–397
56.
57.
M. Maurer, A. Menezes, E. Teske, Analysis of the GHS Weil descent attack on the ECDLP over characteristic two finite fields of composite degree, in Proceedings of INDOCRYPT 2001. LNCS, vol. 2247 (Springer, Berlin, 2001), pp. 195–213
58.
A. Menezes, T. Okamoto, S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inf. Theory 39, 1639–1646 (1993)MathSciNetCrossRefMATH
59.
A. Menezes, T. Okamoto, S.A. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, in STOC 91 (ACM, New York, 1992), pp. 80–89
60.
A. Menezes, M. Qu, Analysis of the Weil descent attack of Gaudry, Hess and Smart, in Proceedings of CT-RSA 2001. LNCS, vol. 2020 (Springer, Berlin, 2001), pp. 308–318
61.
A. Menezes, S.A. Vanstone, The implementation of elliptic curve cryptosystems, in Proceedings of AUSCRYPT 90. LNCS, vol. 453 (Springer, Berlin, 1990), pp. 2–13
62.
V. Miller, Uses of elliptic curves in cryptography, in Proceedings of CRYPTO 85. LNCS, vol. 218 (Springer, Berlin, 1985), pp. 417–426
63.
64.
D. Naccache, N.P. Smart, J. Stern, Projective coordinates leak, in Proceedings of EUROCRYPT 2004. LNCS, vol. 3027 (Springer, Berlin, 2004), pp. 257–267
65.
66.
67.
68.
P.Q. Nguyen, I.E. Shparlinski, The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Des. Codes Cryptogr. 30, 201–217 (2003)MathSciNetCrossRefMATH
69.
T. Oliveira, D.F. Aranha, J.L. Hernandez, F. Rodríguez-Henríquez, Fast point multiplication algorithms for binary elliptic curves with and without precomputation, in Proceedings of SAC 2014. LNCS, vol. 8781 (Springer, Berlin, 2014), pp. 324–344
70.
T. Oliveira, D.F. Aranha, J. López, F, Rodríguez-Henríquez, Improving the performance of the GLS254. Presentation at CHES 2016 rump session (2016)
71.
T. Oliveira, J. López, D.F. Aranha, F. Rodríguez-Henríquez, Two is the fastest prime: lambda coordinates for binary elliptic curves. J. Cryptogr. Eng. 4(1), 3–17 (2014)CrossRef
72.
73.
74.
G. Paoloni, How to benchmark code execution times on Intel IA-32 and IA-64 instruction set architectures. Technical report, Intel Corporation (2010)
75.
C. Petit, M. Kosters, A. Messeng, Algebraic approaches for the elliptic curve discrete logarithm problem over prime fields, in Proceedings of PKC 2016. LNCS, vol. 9615 (Springer, Berlin, 2016), pp. 3–18
76.
R. Sakai, K. Ohgishi, M. Kasahara, Cryptosystems based on pairing over elliptic curve (in Japanese), in The 2001 Symposium on Cryptography and Information Security (2001)
77.
R. Schroeppel, Cryptographic elliptic curve apparatus and method. US Patent 2002/6490352 B1 (2000)
78.
79.
80.
81.
J.A. Solinas, An improved algorithm for arithmetic on a family of elliptic curves, in Proceedings of CRYPTO 97. LNCS, vol. 1294 (Springer, Berlin, 1997), pp. 357–371
82.
83.
84.
J. Taverne, A. Faz-Hernández, D.F. Aranha, F. Rodríguez-Henríquez, D. Hankerson, J. López, Software implementation of binary elliptic curves: impact of the carry-less multiplier on scalar multiplication, in Proceedings of CHES 2011. LNCS, vol. 6917 (Springer, Berlin, 2011), pp. 108–123
85.
86.
Y. Tsunoo, E. Tsujihara, K. Minematsu, H. Miyauchi, Cryptanalysis of block ciphers implemented on computers with cache, in International Symposium on Information Theory and Its Applications (IEEE Information Theory Society, 2002), pp. 803–806
87.
M.D. Velichka, M.J. Jacobson Jr., A. Stein, Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields. Math. Comput. 83(286), 935–963 (2014)
88.
89.
E. Wenger, P. Wolfger, Solving the discrete logarithm of a 113-Bit Koblitz curve with an FPGA cluster, in Proceedings of SAC 2014. LNCS, vol. 8781 (Springer, Berlin, 2014), pp. 363–379
90.
E. Wenger, P. Wolfger, Harder, better, faster, stronger: elliptic curve discrete logarithm computations on FPGAs. J. Cryptogr. Eng. 6(4), 287–297 (2016)CrossRef
91.
M.J. Wiener, R.J. Zuccherato, Faster attacks on elliptic curve cryptosystems, in Proceedings of SAC 98. LNCS, vol. 1556 (Springer, Berlin, 1999), pp. 190–200
Metadata
Title
Koblitz Curves over Quadratic Fields
Authors
Thomaz Oliveira
Julio López
Daniel Cervantes-Vázquez
Francisco Rodríguez-Henríquez
Publication date
25-04-2018
Publisher
Springer US
Published in
Journal of Cryptology / Issue 3/2019
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-018-9294-z

Other articles of this Issue 3/2019

Journal of Cryptology 3/2019 Go to the issue

OriginalPaper

Probabilistic Termination and Composability of Cryptographic Protocols

OriginalPaper

Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ

OriginalPaper

The Magic of ELFs

OriginalPaper

On Black-Box Complexity of Universally Composable Security in the CRS Model

OriginalPaper

Efficient Fully Structure-Preserving Signatures and Shrinking Commitments

OriginalPaper

Beyond Conventional Security in Sponge-Based Authenticated Encryption Modes

Premium Partner

    Image Credits