A generalized formula for calculating bounds for the balanced value of the hyperellip-tic 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 р-value and embedding degrees к = 1,2,..., 10.
Download file
Counter downloads: 282
- Title On bounds for balanced embedding degree
- Headline On bounds for balanced embedding degree
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(32)
- Date:
- DOI
Keywords
криптография, гиперэллиптические кривые, задача дискретного логарифмирования, билинейные спаривания, степень вложения, hyperelliptic curve cryptography, pairings, embedding degree, discrete logarithm problemAuthors
References
Menezes A, Okamoto T., and Vanstone S. A. Reducing elliptic curve logarithms to logarithms in a finite field // IEEE Trans. Inform. Theory. 1993. V. 39. No. 5. P. 1639-1646.
Sakai R., Ohgishi K., and Kasahara M. Cryptosystems Based on Pairing. Okinawa, Japan, 2000.
Joux A. A one round protocol for tripartite Diffie - Hellman // ANTS-IV. LNCS. 2000. V. 1838. P. 385-393.
Boneh D. and Franklin M. K. Identity-based encryption from the Weil pairing // CRYPTO 2001. LNCS. 2001. V.2139. P. 213-229.
Paterson K. G. Cryptography from pairings // Advances in Elliptic Curve Cryptography. Cambridge University Press, 2005. P. 215-252.
HittL. On the minimal embedding field // LNCS. 2007. V.4575. P. 294-301.
Benger N., Charlemagne M., and Freeman D. M. On the security of pairing-friendly Abelian varieties over non-prime fields // LNCS. 2009. V.5671. P. 52-65.
Galbraith S. D., Hess F., and Vercauteren F. Aspects of pairing inversion // IEEE Trans. Inform. Theory. 2008. V. 54. No. 12. P. 5719-5728.
Joux A. A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic // LNCS. 2014. V. 8282. P. 355-379.
Barbulescu R., Gaudry P., Joux A., and Thome E. A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic // LNCS. 2014. V. 8441. P. 1-16.
Frey G. and LangeT. Transfer of discrete logarithms // Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman and Hall/CRC, 2005. P. 529-545.
Miller V. S. The Weil pairing, and its efficient calculation // J. Cryptology. 2004. V. 17. No. 4. P. 235-261.
Freeman D., Scott M., and Teske E. A taxonomy of pairing-friendly elliptic curves // J. Cryptology. 2010. V. 23. No. 2. P. 224-280.
Balakrishnan J., Belding J., ChisholmS., et al. Pairings on hyperelliptic curves. http:// arxiv.org/abs/0908.373. 2009.
Pollard J. M. Monte Carlo methods for index computation (mod p) // Math. Comput. 1978. V. 78. No. 147. P. 918-924.
Pohlig S. C. and Hellman M. E. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (Corresp.) // IEEE Trans. Inform. Theory. 1978. V. 24. No. 1. P. 106-110.
Joux A., Odlyzko A., and Pierrot C. The past, evolving present, and future of the discrete logarithm // Open Problems in Mathematics and Computational Science. Springer International Publishing, 2014. P. 5-36.
Adj G., Menezes A., Oliveira T., and Rodriguez-Henriquez F. Computing discrete logarithms in F36.137 and F36 i63 using Magma // LNCS. 2015. V.9061. P. 3-22.
Adj G., Menezes A, Oliveira T., and Rodriguez-Henriquez F. Weakness of F36i429 and F24304i for discrete logarithm cryptography // Finite Fields and Their Applications. 2015. V. 32. P. 148-170.
Joux A. and Pierrot C. Technical history of discrete logarithms in small characteristic finite fields - The road from subexponential to quasi-polynomial complexity // Des. Codes Cryptography. 2016. V. 78. No. 1. P. 73-85
Pierrot C. The multiple Number Field Sieve with conjugation and generalized Joux - Lercier methods // LNCS. 2015. V.2056. P. 156-170.
Kim T. and Barbulescu R. Extended Tower Number Field Sieve: A New Complexity for Medium Prime Case. Cryptology ePrint Archive, Report 2015/1027. http://ia.cr/2015/ 1027.
Pierrot C. and Barbulescu R. The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields. Cryptology ePrint Archive, Report 2014/147. http://ia.cr/ 2014/147.
Frey G. and Ruck H. G. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves // Math. Comput. 1994. V.62. No. 206. P. 865-874.
Gaudry P., Hess F., and Smart N. P. Constructive and destructive facets of Weil descent on elliptic curves // J. Cryptology. 2002. V. 15. No. 1. P. 19-46.
Semaev I. A. New algorithm for the discrete logarithm problem on elliptic curves. Cryptology ePrint Archive, Report 2015/310. http://ia.cr/2015/310.
Gaudry P., Thome E., TheriaultN., and Diem C. A double large prime variation for small genus hyperelliptic index calculus // Math. Comput. 2007. V. 76. No. 257. P. 475-492.
Enge A. and Gaudry P. A general framework for subexponential discrete logarithm algorithms // Acta Arith. 2000. V. 102. P. 83-103.
Enge A., Gaudry P., and Thome E. An L(1/3) discrete logarithm algorithm for low degree curves // J. Cryptology. 2011. V. 24. No. 1. P. 24-41.
Menezes A. The elliptic curve logarithm problem // Elliptic Curve Public Key Cryptosystems. Boston: Springer US, 1993. P. 61-81.
Lenstra A. K. L Notation // Encyclopedia of Cryptography and Security. Springer, 2011. P. 709-710.
Cantor D. G. Computing in the Jacobian of a hyperelliptic curve // Math. Comput. 1987. V. 48. No. 177. P. 95-101.
Jacobson M., Menezes A., and Stein A. Hyperelliptic curves and cryptography // Fields Institute Communications. 2004. V.41. P. 255-282.
Galbraith S. Pairings // Advances in Elliptic Curve Cryptography. Cambridge University Press, 2005. P. 183-212.
http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r4. pdf - NIST. Recommendation for Key Management, Part 1: General. 2016.
Corless R. M., Gonnet G. H., Hare D. E. G., et al. On the Lambert W function // Adv. Comput. Math. 1996. V.5. No. 1. P. 329-359.
http://www. ecrypt.eu.org/ecrypt2/documents/D.SPA.20.pdf - ECRYPT II. Yearly Report on Algorithms and Keysizes. 2012.
Galbraith S. D., Hess F., and Vercauteren F. Hyperelliptic pairings // LNCS. 2007. V. 4575. P. 108-131.
Galbraith S. D. Supersingular curves in cryptography // LNCS. 2001. V. 2248. P. 495-513.
Freeman D. Constructing pairing-friendly genus 2 curves with ordinary Jacobians // LNCS. 2007. V. 4575. P. 152-176.
Freeman D. A Generalized Brezing - Weng Algorithm for Constructing Pairing-Friendly Ordinary Abelian Varieties. Cryptology ePrint Archive, Report 2008/155. http://ia.cr/ 2008/155.
Kawazoe M. and Takahashi T. Pairing-friendly hyperelliptic curves with ordinary Jacobians of type y2 = x5 + ax // LNCS. 2008. V. 5209. P. 164-177.
Kachisa E. J. Generating more Kawazoe - Takahashi genus 2 pairing-friendly hyperelliptic curves // LNCS. 2010. V.6487. P. 312-326.
Freeman D. M. and Satoh T. Constructing pairing-friendly hyperelliptic curves using Weil restriction // J. Number Theory. 2011. V. 131. No. 5. P. 959-983.
Drylo R. Constructing pairing-friendly genus 2 curves with split Jacobian // LNCS. 2012. V. 7668. P. 431-453.
Freeman D., Stevenhagen P., and Streng M. Abelian varieties with prescribed embedding degree // LNCS. 2008. V.5011. P. 60-73.
Lenstra A. K. and Verheul E. R. Selecting cryptographic key sizes //J. Cryptology. 2001. V. 14. P. 255-293.
www.keylength.com - BlueKrypt: Cryptgraphic Key Length Recommendation. 2016.
On bounds for balanced embedding degree | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 2(32).
Download full-text version
Counter downloads: 1011