{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T18:03:59Z","timestamp":1743098639259,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662464465"},{"type":"electronic","value":"9783662464472"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46447-2_6","type":"book-chapter","created":{"date-parts":[[2015,3,16]],"date-time":"2015-03-16T01:21:25Z","timestamp":1426468885000},"page":"127-149","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Collision of Random Walks and a Refined Analysis of Attacks on the Discrete Logarithm Problem"],"prefix":"10.1007","author":[{"given":"Shuji","family":"Kijima","sequence":"first","affiliation":[]},{"given":"Ravi","family":"Montenegro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,3,17]]},"reference":[{"key":"6_CR1","unstructured":"Bailey, D., Batina, L., Bernstein, D., Birkner, P., Bos, J., Chen, H.-C., Cheng, C.-M., Van Damme, G., de Meulenaer, G., Perez, L.J.D., Fan, J., G\u00fcneysu, T., G\u00fcrkaynak, F., Kleinjung, T., Lange, T., Mentens, N., Niederhagen, R., Paar, C., Regazzoni, F., Schwabe, P., Uhsade, L., Van Herrewege, A., Yang, B-Y.: \u201cBreaking ECC2K-130,\u201d Cryptology ePrint Archive, Report 2009\/541 (2009). \n                      https:\/\/eprint.iacr.org\/2009\/541"},{"key":"6_CR2","unstructured":"Bernstein, D.J., Lange, T.: Two grumpy giants and a baby. In: ANTS X: Proceedings of the 10th International Symposium on Algorithmic Number Theory. Mathematical Sciences Publishers (2013)"},{"key":"6_CR3","unstructured":"Blackburn, S., Scott, S.: The discrete logarithm problem for exponents of bounded height. In: ANTS XI: Proceedings of the 11th International Symposium on Algorithmic Number Theory. LMS J. Comput. Math 17, 148\u2013156 (2014)"},{"key":"6_CR4","unstructured":"Blackburn, S., Murphy, S.: The number of partitions in Pollard Rho, Unpublished note : Later made available as Technical report RHUL-MA-2011-11 (Department of Mathematics, p. 2011. University of London, Royal Holloway (1998)"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1090\/S0025-5718-2012-02641-X","volume":"82","author":"SD Galbraith","year":"2013","unstructured":"Galbraith, S.D., Pollard, J.M., Ruprai, R.S.: Computing discrete logarithms in an interval. Math. Comp. 82, 1181\u20131195 (2013)","journal-title":"Math. Comp."},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/978-3-642-10868-6_22","volume-title":"Cryptography and Coding","author":"S Galbraith","year":"2009","unstructured":"Galbraith, S., Ruprai, R.S.: An improvement to the Gaudry-Schost algorithm for multidimensional discrete logarithm problems. In: Parker, M.G. (ed.) Cryptography and Coding 2009. LNCS, vol. 5921, pp. 368\u2013382. Springer, Heidelberg (2009)"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-540-24847-7_15","volume-title":"Algorithmic Number Theory","author":"P Gaudry","year":"2004","unstructured":"Gaudry, P., Schost, \u00c9.: A low-memory parallel version of Matsuo, Chao, and Tsujii\u2019s algorithm. In: Buell, D.A. (ed.) ANTS 2004. LNCS, vol. 3076, pp. 208\u2013222. Springer, Heidelberg (2004)"},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1214\/ECP.v11-1237","volume":"11","author":"M Hildebrand","year":"2006","unstructured":"Hildebrand, M.: On the Chung-Diaconis-Graham random process. Electron. Comm. Probab. 11, 347\u2013356 (2006)","journal-title":"Electron. Comm. Probab."},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Kim, J-H., Montenegro, R., Tetali, P.: Near Optimal Bounds for Collision in Pollard Rho for Discrete Log. In: IEEE Proc. of the Symposium on Foundations of Computer Science (FOCS 2007), pp. 215\u2013223 (2007)","DOI":"10.1109\/FOCS.2007.38"},{"issue":"2","key":"6_CR10","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1214\/09-AAP625","volume":"20","author":"J-H Kim","year":"2010","unstructured":"Kim, J.-H., Montenegro, R., Peres, Y., Tetali, P.: A Birthday Paradox for Markov chains, with an optimal bound for collision in the Pollard Rho Algorithm for Discrete Logarithm. The Annals of Applied Probability 20(2), 495\u2013521 (2010)","journal-title":"The Annals of Applied Probability"},{"issue":"1","key":"6_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/272991.272995","volume":"8","author":"M Matsumoto","year":"1998","unstructured":"Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation 8(1), 3\u201330 (1998)","journal-title":"ACM Transactions on Modeling and Computer Simulation"},{"key":"6_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/11792086_40","volume-title":"Algorithmic Number Theory","author":"SD Miller","year":"2006","unstructured":"Miller, S.D., Venkatesan, R.: Spectral analysis of Pollard rho collisions. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 573\u2013581. Springer, Heidelberg (2006)"},{"key":"6_CR13","unstructured":"Montenegro, R., Tetali, P.: How long does it take to catch a wild kangaroo?. In: Proc. of 41st ACM Symposium on Theory of Computing (STOC 2009), pp. 553\u2013559 (2009). Citations refer to an improved version at \n                      http:\/\/arxiv.org\/pdf\/0812.0789v2.pdf"},{"issue":"1","key":"6_CR14","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF02252867","volume":"2","author":"K Nishimura","year":"1990","unstructured":"Nishimura, K., Shibuya, M.: Probability to meet in the middle. Journal of Cryptology 2(1), 13\u201322 (1990)","journal-title":"Journal of Cryptology"},{"issue":"143","key":"6_CR15","first-page":"918","volume":"32","author":"J Pollard","year":"1978","unstructured":"Pollard, J.: Monte Carlo methods for index computation mod p. Mathematics of Computation 32(143), 918\u2013924 (1978)","journal-title":"Mathematics of Computation"},{"issue":"4","key":"6_CR16","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s001450010010","volume":"13","author":"J Pollard","year":"2000","unstructured":"Pollard, J.: Kangaroos, Monopoly and Discrete Logarithms. Journal of Cryptology 13(4), 437\u2013447 (2000)","journal-title":"Journal of Cryptology"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/3-540-69053-0_18","volume-title":"Advances in Cryptology - EUROCRYPT \u201997","author":"V Shoup","year":"1997","unstructured":"Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256\u2013266. Springer, Heidelberg (1997)"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/BFb0054891","volume-title":"Algorithmic Number Theory","author":"E Teske","year":"1998","unstructured":"Teske, E.: Speeding up Pollard\u2019s rho method for computing discrete logarithms. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 541\u2013554. Springer, Heidelberg (1998)"},{"key":"6_CR19","series-title":"Understanding Complex Systems","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-319-00155-5","volume-title":"Macroscopic Models for Vehicular Flows and Crowd Dynamics: Theory and Applications","author":"MD Rosini","year":"2013","unstructured":"Rosini, M.D.: Applications. In: Rosini, M.D. (ed.) Macroscopic Models for Vehicular Flows and Crowd Dynamics: Theory and Applications. UCS, vol. 12, pp. 217\u2013226. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Public-Key Cryptography -- PKC 2015"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46447-2_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T11:49:24Z","timestamp":1559130564000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46447-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662464465","9783662464472"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46447-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"17 March 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}