ГлавнаяАрхивГраницы сбалансированной степени вложения для криптографии на билинейных спариваниях

Границы сбалансированной степени вложения для криптографии на билинейных спариваниях | Прикладная дискретная математика. 2016. № 2(32).

Вводится формула для расчёта границ сбалансированной степени вложения гиперэллиптической кривой. Вычислены текущие границы для кривых рода 1-3. Для кривых с известными алгоритмами генерации, наименьшими р-значениями и степенями вложения от 1 до 10 вычислен диапазон значений, которому принадлежит уровень безопасности кривой.
  • Title Границы сбалансированной степени вложения для криптографии на билинейных спариваниях
  • Headline Границы сбалансированной степени вложения для криптографии на билинейных спариваниях
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(32)
  • Date:
  • DOI
Ключевые слова
криптография, гиперэллиптические кривые, задача дискретного логарифмирования, билинейные спаривания, степень вложения, hyperelliptic curve cryptography, pairings, embedding degree, discrete logarithm problem
Авторы
Ссылки
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.
Границы сбалансированной степени вложения для криптографии на билинейных спариваниях | Прикладная дискретная математика. 2016. № 2(32).
Границы сбалансированной степени вложения для криптографии на билинейных спариваниях | Прикладная дискретная математика. 2016. № 2(32).