Pairing inversion for finding discrete logarithms. (English. Russian original) Zbl 1357.94063
J. Math. Sci., New York 206, No. 6, 734-741 (2015); translation from Fundam. Prikl. Mat. 18, No. 4, 185-195 (2013).
Summary: This paper proposes an inversion algorithm for pairings. This technique can be used for breaking the Diffie-Hellman protocol on elliptic curves and for solving the discrete logarithm problem on some curves that satisfy GOST P.34.10-2012.
References:
| [1] | M. Bardet, J. C. Faugère, and B. Salvy, Complexity of Gröbner Basis Computation for Semi-Regular Overdetermined Sequences over F2with Solutions in F2, INRIA, rapport de recherche No. 5049 (Decembre 2003). · Zbl 0316.68031 |
| [2] | E. R. Canfield, P. Erdös, and C. Pomerance, “On a problem of Oppenheim concerning ‘Factorisatio Numerorum’,” J. Number Theory, 17, 1-28 (1983). · Zbl 0513.10043 · doi:10.1016/0022-314X(83)90002-1 |
| [3] | M. A. Cherepnev, “On the connection between discrete logarithms and the Diffie-Hellman problem,” Discrete Math., 8, No. 3, 22-30 (1996). |
| [4] | H. Cohen, G. Frey et al., Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman and Hall, London (2006). · Zbl 1082.94001 |
| [5] | J. H. Davenport, On the Integration of Algebraic Functions, Lect. Notes Comput. Sci., Vol. 102, Springer, Berlin (1979). · Zbl 0411.34002 |
| [6] | J. C. Faugère, M. S. Din, and T. Verron, “On the complexity of computing Gröbner basis for quasi-homogeneous systems,” in: ISSAC’13, June 26-29, 2013, Boston, Massachusetts, USA. · Zbl 1360.68930 |
| [7] | K. Ford, S. V. Konyagin, and F. Luca, “Prime chains and Pratt trees,” Geom. Funct. Anal., 20, 1231-1258 (2010). · Zbl 1218.11085 · doi:10.1007/s00039-010-0089-0 |
| [8] | S. Galbraith, F. Hess, and F. Vercauteren, “Aspects of pairing inversion,” IEEE Trans., 54, No. 12, 5719-5728 (2008). · Zbl 1189.14032 |
| [9] | I. S. Gradshteyn and I. M. Ryzhik, Tables of Integrals, Series, and Products, Academic Press, San Diego (2000), pp. 1111-1112. · Zbl 0981.65001 |
| [10] | F. Hess, “A note on the Tate pairing of curves over finite fields,” Arch. Math. (Basel), 82, 28-32 (2004). · Zbl 1051.11030 · doi:10.1007/s00013-003-4773-2 |
| [11] | Hess, F.; Galbraith, SD (ed.); Paterson, KG (ed.), Pairing lattices, No. 5209, 18-38 (2008), Berlin · Zbl 1186.94444 · doi:10.1007/978-3-540-85538-5_2 |
| [12] | V. S. Miller, Short Programs for Functions on Curves, unpublished manuscript (1986), http://crypto.stanford.edu/miller/. · Zbl 1189.14032 |
| [13] | V. Pratt, “Every prime has a succinct certificate,” SIAM J. Comput., 4, No. 3, 214-220 (1975). · Zbl 0316.68031 · doi:10.1137/0204018 |
| [14] | B. I. Selivanov, “On waiting time in the scheme random allocation of coloured particles,” Discrete Math. Appl., 5, No. 1, 73-82 (1995). · Zbl 0840.60015 · doi:10.1515/dma.1995.5.1.73 |
| [15] | J. Silverman, The Arithmetic of Elliptic Curves, Springer, Berlin (1986). · Zbl 0585.14026 · doi:10.1007/978-1-4757-1920-8 |
| [16] | O. N. Vasilenko, Number-Theoretic Algorithms in Cryptography (2006). · Zbl 0513.10043 |
| [17] | F. Vercauteren, “The hidden root problem,” in: S. D. Galbraith and K. G. Paterson, eds., Pairing Based Cryptography — Pairing 2008, Springer, Berlin (2008), Lect. Notes Comput. Sci., Vol. 5209, pp. 89-99, https://eprint.iacr.org/2008/261.pdf. · Zbl 1186.94474 |
| [18] | F. Vercauteren, “Optimal pairings,” IEEE Trans. Inform. Theory, 56, No. 1, 455-461 (2010), https://eprint.iacr.org/2008/096.pdf. · Zbl 1366.94540 |
| [19] | B. L. van der Waerden, Algebra, Springer, Berlin (1971). · Zbl 0221.12001 |
| [20] | C.-A. Zhao, F. Zhang, and J. Huang, A Note on the Ate Pairing Cryptology, http://eprint.iacr.org/2007/247.pdf. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
