×

Improved algorithm for the isogeny problem for ordinary elliptic curves. (English) Zbl 1316.11113

Summary: A low storage algorithm for constructing isogenies between ordinary elliptic curves was proposed by Galbraith, Hess and Smart (GHS) S. D. Galbraith et al., Eurocrypt 2002, Lect. Notes Comput. Sci. 2332, 29–44 (2002; Zbl 1055.94013)]. We give an improvement of this algorithm by modifying the pseudorandom walk so that lower-degree isogenies are used more frequently. This is motivated by the fact that high degree isogenies are slower to compute than low degree ones. We analyse the running time of the parallel collision search algorithm when the partitioning is uneven. We also give experimental results. We conclude that our algorithm is around 14 times faster than the GHS algorithm when constructing horizontal isogenies between random isogenous elliptic curves over a 160-bit prime field. The results apply to generic adding walks and the more general group action inverse problem; a speed-up is obtained whenever the cost of computing edges in the graph varies significantly.

MSC:

11Y16 Number-theoretic algorithms; complexity
11G20 Curves over finite and local fields
14G50 Applications to coding theory and cryptography of arithmetic geometry
14H52 Elliptic curves
68W20 Randomized algorithms

Citations:

Zbl 1055.94013

Software:

MersenneTwister
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bailey, D.V., Batina, L., Bernstein, D.J., Birkner, P., Bos, J.W., Chen, H.C., Cheng, C.M., van Damme, G., de Meulenaer, G., Perez, L.J.D., Fan, J., Gneysu, T., Gurkaynak, F., Kleinjung, T., Lange, T., Mentens, N., Niederhagen, R., Paar, C., Regazzoni, F., Schwabe, P., Uhsadel, L., Herrewege, A.V., Yang, B.Y.: Breaking ECC2K-130. Cryptology ePrint Archive, Report 2009/541 (2009). http://eprint.iacr.org/2009/541 · Zbl 1213.94136
[2] Bernstein, D.J., Lange, T.: Two grumpy giants and a baby. Tenth Algorithmic Number Theory Symposium ANTS-X, In (2012) · Zbl 1344.11083
[3] Biasse, J.F.: Improvements in the computation of ideal class groups of imaginary quadratic number fields. Adv. Math. Commun. 4(2), 141-154 (2010). doi:10.3934/amc.2010.4.141 · Zbl 1257.11108
[4] Bisson, G., Sutherland, A.V.: Computing the endomorphism ring of an ordinary elliptic curve over a finite field. J. Number Theory 131(5), 815-831 (2011). doi:10.1016/j.jnt.2009.11.003. http://www.sciencedirect.com/science/article/pii/S0022314X09002789 · Zbl 1225.11085
[5] Bisson, G., Sutherland, A.V.: A low-memory algorithm for finding short product representations in finite groups. Des. Codes Cryptogr. 63(1), 1-13 (2012). doi:10.1007/s10623-011-9527-8 · Zbl 1246.20031 · doi:10.1007/s10623-011-9527-8
[6] Blackburn, S.R., Murphy, S.: The number of partitions in Pollard rho (1998). Preprint
[7] Brent, R.P., Pollard, J.M.: Factorization of the eighth Fermat number. Math. Comp. 36(154), 627-630 (1981). doi:10.2307/2007666 · Zbl 0476.10007 · doi:10.2307/2007666
[8] Childs, A.M., Jao, D., Soukharev, V.: Constructing elliptic curve isogenies in quantum subexponential time (2010). http://arxiv.org/abs/1012.4019v1 · Zbl 1283.81046
[9] Cohen, H., Lenstra Jr., H.W.: Heuristics on class groups of number fields. In: Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983), Lecture Notes in Mathemetics, vol. 1068, pp. 33-62. Springer, Berlin (1984). doi:10.1007/BFb0099440
[10] Couveignes, J.M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006). http://eprint.iacr.org/2006/291
[11] Dai, J.J., Hildebrand, M.V.: Random random walks on the integers mod \[n\]. Stat. Probab. Lett. 35(4), 371-379 (1997). doi:10.1016/S0167-7152(97)00035-7 · Zbl 0892.60081
[12] Debiao, H., Jianhua, C., Jin, H.: An authenticated key agreement protocol using isogenies between elliptic curves. Int. J. Comput. Commun. Control 6, 258-265 (2011)
[13] Galbraith, S.D.: Constructing isogenies between elliptic curves over finite fields. LMS J. Comput. Math. 2, 118-138 (1999). (electronic) · Zbl 1018.11028
[14] Galbraith, S.D., Hess, F., Smart, N.P.: Extending the GHS Weil descent attack. In: Advances in cryptology-EUROCRYPT 2002 (Amsterdam), Lecture Notes in Computer Science, vol. 2332, pp. 29-44. Springer, Berlin (2002). doi:10.1007/3-540-46035-7_3 · Zbl 1055.94013
[15] Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Improving the parallelized Pollard lambda search on binary anomalous curves. Math. Comput. 69(232), 1699-1705 (2000) · Zbl 1101.14325
[16] Goldreich, O.: Lecture notes: Randomized methods in computation (2001). http://www.wisdom.weizmann.ac.il/ oded/rnd.html
[17] Harris, B.: Probability distributions related to random mappings. Ann. Math. Stat. 31, 1045-1062 (1960) · Zbl 0158.34905 · doi:10.1214/aoms/1177705677
[18] Jacobson Jr., M.J., Ramachandran, S., Williams, H.C.: Numerical results on class groups of imaginary quadratic fields. In: Algorithmic number theory, Lecture Notes in Computer Science, vol. 4076, pp. 87-101. Springer, Berlin (2006). doi:10.1007/11792086_7 · Zbl 1143.11370
[19] Jao, D., Miller, S.D., Venkatesan, R.: Do all elliptic curves of the same order have the same difficulty of discrete log? In: Advances in cryptology-ASIACRYPT 2005, Lecture Notes in Computer Science, vol. 3788, pp. 21-40. Springer, Berlin (2005). doi:10.1007/11593447_2 · Zbl 1154.94401
[20] Jao, D., Miller, S.D., Venkatesan, R.: Expander graphs based on GRH with an application to elliptic curve cryptography. J. Number Theory 129(6), 1491-1504 (2009). doi:10.1016/j.jnt.2008.11.006 · Zbl 1228.05167 · doi:10.1016/j.jnt.2008.11.006
[21] Knuth, D.E.: The Art of Computer Programming: Seminumerical Algorithms, vol. 2, 3rd edn. Addison-Wesley, Boston (1997) · Zbl 0895.65001
[22] Koblitz, A.H., Koblitz, N., Menezes, A.: Elliptic curve cryptography: the serpentine course of a paradigm shift. J. Number Theory 131(5), 781-814 (2011). doi:10.1016/j.jnt.2009.01.006 · Zbl 1213.94117 · doi:10.1016/j.jnt.2009.01.006
[23] Kohel, D.: Endomorphism rings of elliptic curves over finite fields. Ph.D. thesis, University of California at Berkeley (1996) · Zbl 0158.34905
[24] Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8(1), 3-30 (1998) · Zbl 0917.65005 · doi:10.1145/272991.272995
[25] Montenegro, R.: A simple method for precisely determining complexity of many birthday attacks (2012). http://faculty.uml.edu/rmontenegro/research/intersectionheuristic-abstract.pdf
[26] Pohl, I.: Bi-directional and heuristic search in path problems. Technical Report 104, Stanford Linear Accelerator Center, Stanford, California (1969) · Zbl 0188.53001
[27] Pollard, J.M.: A Monte Carlo method for factorization, Nordisk Tidskr. BIT 15(3), 331-334 (1975) · Zbl 0312.10006 · doi:10.1007/BF01933667
[28] Pollard, J.M.: Monte Carlo methods for index computation (mod \[p)\]. Math. Comp. 32(143), 918-924 (1978) · Zbl 0382.10001
[29] Rapoport, A.: Cycle distributions in random nets. Bull. Math. Biol. 10, 145-157 (1948)
[30] Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, report 2006/145 (2006). http://eprint.iacr.org/2006/145
[31] Schoof, R.: Quadratic fields and factorization. In: Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, pp. 235-286. Math. Centrum, Amsterdam (1982) · Zbl 0527.12003
[32] Schulte-Geers, E.: Collision search in a random mapping: some asymptotic results. Presentation at ECC 2000 (Essen, Germany) (2000)
[33] Soong, T.T.: Fundamentals of Probability and Statistics for Engineers. Wiley, Hoboken (2004) · Zbl 1049.62124
[34] Stolbunov, A.: ClassEll package, ver. 0.1. http://www.item.ntnu.no/people/personalpages/phd/anton/software, last visited 15/12/2012 · Zbl 1213.94136
[35] Stolbunov, A.: Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Adv. Math. Commun. 4(2), 215-235 (2010). doi:10.3934/amc.2010.4.215 · Zbl 1213.94136 · doi:10.3934/amc.2010.4.215
[36] Stolbunov, A.: Cryptographic schemes based on isogenies. Ph.D. thesis, Norwegian University of Science and Technology (NTNU) (2012) · Zbl 1099.14012
[37] Strutt [Lord Rayleigh], J.W.: On the resultant of a large number of vibrations of the same pitch and of arbitrary phase. Philos. Mag. 10(60), 73-78 (1880)
[38] Tate, J.: Endomorphisms of abelian varieties over finite fields. Invent. Math. 2, 134-144 (1966) · Zbl 0147.20303 · doi:10.1007/BF01404549
[39] Teske, E.: On random walks for Pollard’s rho method. Math. Comp. 70(234), 809-825 (2001). doi:10.1090/S0025-5718-00-01213-8 · Zbl 1029.11071
[40] Teske, E.: An elliptic curve trapdoor system. J. Cryptol. 19(1), 115-133 (2006). doi:10.1007/s00145-004-0328-3 · Zbl 1099.14012 · doi:10.1007/s00145-004-0328-3
[41] van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1-28 (1999). doi:10.1007/PL00003816 · Zbl 0992.94028 · doi:10.1007/PL00003816
[42] Wang, T.: Integer hash function. http://www.concentric.net/ Ttwang/tech/inthash.htm, last visited 08/06/2010
[43] Waterhouse, W.C.: Abelian varieties over finite fields. Ann. Sci. École Norm. Sup. 4(2), 521-560 (1969) · Zbl 0188.53001
[44] Wiener, M.J., Zuccherato, R.J.: Faster attacks on elliptic curve cryptosystems. In: S.E. Tavares, H. Meijer (eds.) SAC 1998, LNCS, vol. 1556, pp. 190-200. Springer (1998) · Zbl 1025.94511
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.