On bounds for balanced embedding degree

S. A. Novoselov

Prikladnaâ diskretnaâ matematika, no. 2 (2016), pp. 63-86.

Résumé

A generalized formula for calculating bounds for the balanced value of the hyperelliptic curve embedding degree is proved. Using this formula we give bounds for curves of genus 1–3 over finite fields with the small, medium and big characteristic. We also compute possible range of security level for curves with known generation methods, minimal $\rho$-value and embedding degrees $k=1,2,\dots,10$.

Détail

Keywords: hyperelliptic curve cryptography, pairings, embedding degree, discrete logarithm problem.

Bibliographie

[1] Menezes A., Okamoto T., Vanstone S. A., “Reducing elliptic curve logarithms to logarithms in a finite field”, IEEE Trans. Inform. Theory, 39:5 (1993), 1639–1646 | DOI | MR | Zbl

[2] Sakai R., Ohgishi K., Kasahara M., Cryptosystems Based on Pairing, Okinawa, Japan, 2000

[3] Joux A., “A one round protocol for tripartite Diffie–Hellman”, ANTS-IV, LNCS, 1838, 2000, 385–393 | MR | Zbl

[4] Boneh D., Franklin M. K., “Identity-based encryption from the Weil pairing”, CRYPTO 2001, LNCS, 2139, 2001, 213–229 | MR | Zbl

[5] Paterson K. G., “Cryptography from pairings”, Advances in Elliptic Curve Cryptography, Cambridge University Press, 2005, 215–252 | DOI | MR

[6] Hitt L., “On the minimal embedding field”, LNCS, 4575, 2007, 294–301 | MR | Zbl

[7] Benger N., Charlemagne M., Freeman D. M., “On the security of pairing-friendly Abelian varieties over non-prime fields”, LNCS, 5671, 2009, 52–65 | MR | Zbl

[8] Galbraith S. D., Hess F., Vercauteren F., “Aspects of pairing inversion”, IEEE Trans. Inform. Theory, 54:12 (2008), 5719–5728 | DOI | MR | Zbl

[9] Joux A., “A new index calculus algorithm with complexity $L(1/4+\mathrm o(1))$ in small characteristic”, LNCS, 8282, 2014, 355–379 | MR | Zbl

[10] Barbulescu R., Gaudry P., Joux A., Thomé E., “A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic”, LNCS, 8441, 2014, 1–16 | MR | Zbl

[11] Frey G., Lange T., “Transfer of discrete logarithms”, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman and Hall/CRC, 2005, 529–545 | DOI | MR

[12] Miller V. S., “The Weil pairing, and its efficient calculation”, J. Cryptology, 17:4 (2004), 235–261 | DOI | MR | Zbl

[13] Freeman D., Scott M., Teske E., “A taxonomy of pairing-friendly elliptic curves”, J. Cryptology, 23:2 (2010), 224–280 | DOI | MR | Zbl

[14] Balakrishnan J., Belding J., Chisholm S., et al., Pairings on hyperelliptic curves, 2009, arXiv: 0908.3731

[15] Pollard J. M., “Monte Carlo methods for index computation $\pmod p$”, Math. Comput., 78:147 (1978), 918–924 | MR

[16] Pohlig S. C., Hellman M. E., “An improved algorithm for computing logarithms over GF$(p)$ and its cryptographic significance (Corresp.)”, IEEE Trans. Inform. Theory, 24:1 (1978), 106–110 | DOI | MR | Zbl

[17] Joux A., Odlyzko A., Pierrot C., “The past, evolving present, and future of the discrete logarithm”, Open Problems in Mathematics and Computational Science, Springer International Publishing, 2014, 5–36 | MR | Zbl

[18] Adj G., Menezes A., Oliveira T., Rodríguez-Henríquez F., “Computing discrete logarithms in $\mathbb F_{3^{6\cdot137}}$ and $\mathbb F_{3^{6\cdot163}}$ using Magma”, LNCS, 9061, 2015, 3–22 | MR | Zbl

[19] Adj G., Menezes A., Oliveira T., Rodríguez-Henríquez F., “Weakness of $\mathbb F_{3^{6\cdot1429}}$ and $\mathbb F_{2^{4\cdot3041}}$ for discrete logarithm cryptography”, Finite Fields and Their Applications, 32 (2015), 148–170 | DOI | MR | Zbl

[20] Joux A., Pierrot C., “Technical history of discrete logarithms in small characteristic finite fields – The road from subexponential to quasi-polynomial complexity”, Des. Codes Cryptography, 78:1 (2016), 73–85 | DOI | MR | Zbl

[21] Pierrot C., “The multiple Number Field Sieve with conjugation and generalized Joux–Lercier methods”, LNCS, 2056, 2015, 156–170 | MR

[22] Kim T., Barbulescu R., Extended Tower Number Field Sieve: A New Complexity for Medium Prime Case, Cryptology ePrint Archive; http://eprint.iacr.org/2015/1027

[23] Pierrot C., Barbulescu R., The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields., Cryptology ePrint Archive: http://eprint.iacr.org/2014/147

[24] Frey G., Rück H. G., “A remark concerning $m$-divisibility and the discrete logarithm in the divisor class group of curves”, Math. Comput., 62:206 (1994), 865–874 | MR | Zbl

[25] Gaudry P., Hess F., Smart N. P., “Constructive and destructive facets of Weil descent on elliptic curves”, J. Cryptology, 15:1 (2002), 19–46 | DOI | MR

[26] Semaev I. A., New algorithm for the discrete logarithm problem on elliptic curves, Cryptology ePrint Archive: http://eprint.iacr.org/2015/310

[27] Gaudry P., Thomé E., Thériault N., Diem C., “A double large prime variation for small genus hyperelliptic index calculus”, Math. Comput., 76:257 (2007), 475–492 | DOI | MR | Zbl

[28] Enge A., Gaudry P., “A general framework for subexponential discrete logarithm algorithms”, Acta Arith., 102 (2000), 83–103 | DOI | MR

[29] Enge A., Gaudry P., Thomé E., “An $L(1/3)$ discrete logarithm algorithm for low degree curves”, J. Cryptology, 24:1 (2011), 24–41 | DOI | MR | Zbl

[30] Menezes A., “The elliptic curve logarithm problem”, Elliptic Curve Public Key Cryptosystems, Springer US, Boston, 1993, 61–81 | DOI

[31] Lenstra A. K., “$L$ Notation”, Encyclopedia of Cryptography and Security, Springer, 2011, 709–710

[32] Cantor D. G., “Computing in the Jacobian of a hyperelliptic curve”, Math. Comput., 48:177 (1987), 95–101 | DOI | MR | Zbl

[33] Jacobson M., Menezes A., Stein A., “Hyperelliptic curves and cryptography”, Fields Institute Communications, 41 (2004), 255–282 | MR | Zbl

[34] Galbraith S., “Pairings”, Advances in Elliptic Curve Cryptography, Cambridge University Press, 2005, 183–212 | DOI | MR

[35] NIST. Recommendation for Key Management, Part 1: General, , 2016 http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r4.pdf

[36] Corless R. M., Gonnet G. H., Hare D. E. G., et al., “On the Lambert $W$ function”, Adv. Comput. Math., 5:1 (1996), 329–359 | DOI | MR | Zbl

[37] ECRYPT II. Yearly Report on Algorithms and Keysizes, , 2012 http://www.ecrypt.eu.org/ecrypt2/documents/D.SPA.20.pdf

[38] Galbraith S. D., Hess F., Vercauteren F., “Hyperelliptic pairings”, LNCS, 4575, 2007, 108–131 | MR | Zbl

[39] Galbraith S. D., “Supersingular curves in cryptography”, LNCS, 2248, 2001, 495–513 | MR | Zbl

[40] Freeman D., “Constructing pairing-friendly genus 2 curves with ordinary Jacobians”, LNCS, 4575, 2007, 152–176 | MR | Zbl

[41] Freeman D., A Generalized Brezing–Weng Algorithm for Constructing Pairing-Friendly Ordinary Abelian Varieties, Cryptology ePrint Archive: http://eprint.iacr.org/2008/155 | MR

[42] Kawazoe M., Takahashi T., “Pairing-friendly hyperelliptic curves with ordinary Jacobians of type $y^2=x^5+ax$”, LNCS, 5209, 2008, 164–177 | MR | Zbl

[43] Kachisa E. J., “Generating more Kawazoe–Takahashi genus 2 pairing-friendly hyperelliptic curves”, LNCS, 6487, 2010, 312–326 | MR | Zbl

[44] Freeman D. M., Satoh T., “Constructing pairing-friendly hyperelliptic curves using Weil restriction”, J. Number Theory, 131:5 (2011), 959–983 | DOI | MR | Zbl

[45] Drylo R., “Constructing pairing-friendly genus 2 curves with split Jacobian”, LNCS, 7668, 2012, 431–453 | MR | Zbl

[46] Freeman D., Stevenhagen P., Streng M., “Abelian varieties with prescribed embedding degree”, LNCS, 5011, 2008, 60–73 | MR | Zbl

[47] Lenstra A. K., Verheul E. R., “Selecting cryptographic key sizes”, J. Cryptology, 14 (2001), 255–293 | DOI | MR | Zbl

[48] BlueKrypt: Cryptgraphic Key Length Recommendation, , 2016 http://www.keylength.com