Improved algorithm for the isogeny problem for ordinary elliptic curves
详细信息 查看全文
- 作者：Steven Galbraith (1)
Anton Stolbunov (2) - 关键词：Elliptic curve ; Isogeny ; Class group ; Group action ; 11Y16 ; 11G20 ; 14G50 ; 68W20
- 刊名：Applicable Algebra in Engineering, Communication and Computing
- 出版年：2013
- 出版时间：June 2013
- 年：2013
- 卷：24
- 期：2
- 页码：107-131
- 全文大小：509KB
- 参考文献：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
2. Bernstein, D.J., Lange, T.: Two grumpy giants and a baby. Tenth Algorithmic Number Theory Symposium ANTS-X, In (2012)
3. Biasse, J.F.: Improvements in the computation of ideal class groups of imaginary quadratic number fields. Adv. Math. Commun. 4(2), 141鈥?54 (2010). doi:10.3934/amc.2010.4.141
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鈥?31 (2011). doi:10.1016/j.jnt.2009.11.003 . www.sciencedirect.com/science/article/pii/S0022314X09002789" class="a-plus-plus">http://www.sciencedirect.com/science/article/pii/S0022314X09002789
5. Bisson, G., Sutherland, A.V.: A low-memory algorithm for finding short product representations in finite groups. Des. Codes Cryptogr. 63(1), 1鈥?3 (2012). doi:10.1007/s10623-011-9527-8 CrossRef
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鈥?30 (1981). doi:10.2307/2007666 CrossRef
8. Childs, A.M., Jao, D., Soukharev, V.: Constructing elliptic curve isogenies in quantum subexponential time (2010). http://arxiv.org/abs/1012.4019v1
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鈥?2. 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鈥?79 (1997). doi:10.1016/S0167-7152(97)00035-7
12. Debiao, H., Jianhua, C., Jin, H.: An authenticated key agreement protocol using isogenies between elliptic curves. Int. J. Comput. Commun. Control 6, 258鈥?65 (2011)
13. Galbraith, S.D.: Constructing isogenies between elliptic curves over finite fields. LMS J. Comput. Math. 2, 118鈥?38 (1999). (electronic)
14. Galbraith, S.D., Hess, F., Smart, N.P.: Extending the GHS Weil descent attack. In: Advances in cryptology鈥揈UROCRYPT 2002 (Amsterdam), Lecture Notes in Computer Science, vol. 2332, pp. 29鈥?4. Springer, Berlin (2002). doi:10.1007/3-540-46035-7_3
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鈥?705 (2000)
16. Goldreich, O.: Lecture notes: Randomized methods in computation (2001). www.wisdom.weizmann.ac.il/~oded/rnd.html" class="a-plus-plus">http://www.wisdom.weizmann.ac.il/~oded/rnd.html
17. Harris, B.: Probability distributions related to random mappings. Ann. Math. Stat. 31, 1045鈥?062 (1960) CrossRef
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鈥?01. Springer, Berlin (2006). doi:10.1007/11792086_7
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鈥揂SIACRYPT 2005, Lecture Notes in Computer Science, vol. 3788, pp. 21鈥?0. Springer, Berlin (2005). doi:10.1007/11593447_2
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鈥?504 (2009). doi:10.1016/j.jnt.2008.11.006 CrossRef
21. Knuth, D.E.: The Art of Computer Programming: Seminumerical Algorithms, vol. 2, 3rd edn. Addison-Wesley, Boston (1997)
22. Koblitz, A.H., Koblitz, N., Menezes, A.: Elliptic curve cryptography: the serpentine course of a paradigm shift. J. Number Theory 131(5), 781鈥?14 (2011). doi:10.1016/j.jnt.2009.01.006 CrossRef
23. Kohel, D.: Endomorphism rings of elliptic curves over finite fields. Ph.D. thesis, University of California at Berkeley (1996)
24. Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8(1), 3鈥?0 (1998) CrossRef
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)
27. Pollard, J.M.: A Monte Carlo method for factorization, Nordisk Tidskr. BIT 15(3), 331鈥?34 (1975) CrossRef
28. Pollard, J.M.: Monte Carlo methods for index computation (mod $p$ ). Math. Comp. 32(143), 918鈥?24 (1978)
29. Rapoport, A.: Cycle distributions in random nets. Bull. Math. Biol. 10, 145鈥?57 (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鈥?86. Math. Centrum, Amsterdam (1982)
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)
34. Stolbunov, A.: ClassEll package, ver. 0.1. www.item.ntnu.no/people/personalpages/phd/anton/software" class="a-plus-plus">http://www.item.ntnu.no/people/personalpages/phd/anton/software, last visited 15/12/2012
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鈥?35 (2010). doi:10.3934/amc.2010.4.215 CrossRef
36. Stolbunov, A.: Cryptographic schemes based on isogenies. Ph.D. thesis, Norwegian University of Science and Technology (NTNU) (2012)
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鈥?8 (1880)
38. Tate, J.: Endomorphisms of abelian varieties over finite fields. Invent. Math. 2, 134鈥?44 (1966) CrossRef
39. Teske, E.: On random walks for Pollard鈥檚 rho method. Math. Comp. 70(234), 809鈥?25 (2001). doi:10.1090/S0025-5718-00-01213-8
40. Teske, E.: An elliptic curve trapdoor system. J. Cryptol. 19(1), 115鈥?33 (2006). doi:10.1007/s00145-004-0328-3 CrossRef
41. van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1鈥?8 (1999). doi:10.1007/PL00003816 CrossRef
42. Wang, T.: Integer hash function. www.concentric.net/~Ttwang/tech/inthash.htm" class="a-plus-plus">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鈥?60 (1969)
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鈥?00. Springer (1998) - 作者单位：Steven Galbraith (1)
Anton Stolbunov (2)
1. Mathematics Department, University of Auckland, Auckland, New Zealand
2. Department of Telematics, Norwegian University of Science and Technology, Trondheim, Norway - ISSN：1432-0622
文摘
A low storage algorithm for constructing isogenies between ordinary elliptic curves was proposed by Galbraith, Hess and Smart (GHS). 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.