{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T13:47:27Z","timestamp":1768744047692,"version":"3.49.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,9,12]],"date-time":"2021-09-12T00:00:00Z","timestamp":1631404800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,12]],"date-time":"2021-09-12T00:00:00Z","timestamp":1631404800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006365","name":"Universidad de Cantabria","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006365","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cryptogr. Commun."],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we study the linear congruential generator on elliptic curves from the cryptographic point of view. We show that if sufficiently many of the most significant bits of the <jats:italic>composer<\/jats:italic> and of three consecutive values of the sequence are given, then one can recover the <jats:italic>seed<\/jats:italic> and the <jats:italic>composer<\/jats:italic> (even in the case where the elliptic curve is private). The results are based on lattice reduction techniques and improve some recent approaches of the same security problem. We also estimate limits of some heuristic approaches, which still remain much weaker than those known for nonlinear congruential generators. Several examples are tested using implementations of ours algorithms.<\/jats:p>","DOI":"10.1007\/s12095-021-00535-6","type":"journal-article","created":{"date-parts":[[2021,9,12]],"date-time":"2021-09-12T13:05:37Z","timestamp":1631451937000},"page":"505-525","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Attacking the linear congruential generator on elliptic curves via lattice techniques"],"prefix":"10.1007","volume":"14","author":[{"given":"Jaime","family":"Gutierrez","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,12]]},"reference":[{"key":"535_CR1","doi-asserted-by":"crossref","unstructured":"Avanzi, R., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K.K.: Elliptic and hyperelliptic curve crytography: Theory and practice. CRC Press (2005)","DOI":"10.1201\/9781420034981"},{"key":"535_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L Babai","year":"1986","unstructured":"Babai, L.: On lovasz lattice reduction and the nearest lattice point problem. Combinatorica 6, 1\u20136 (1986)","journal-title":"Combinatorica"},{"key":"535_CR3","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-59435-9_3","volume-title":"Pseudorandom Sequences from Elliptic Curves. Finite Fields with Applications to Coding Theory Cryptography and Related Areas","author":"P Beelen","year":"2002","unstructured":"Beelen, P., Doumen, J.: Pseudorandom Sequences from Elliptic Curves. Finite Fields with Applications to Coding Theory Cryptography and Related Areas, pp 37\u201352. Springer, Berlin (2002)"},{"key":"535_CR4","doi-asserted-by":"publisher","first-page":"1471","DOI":"10.1090\/S0025-5718-04-01698-9","volume":"74","author":"S Blackburn","year":"2005","unstructured":"Blackburn, S., Gomez-Perez, D., Gutierrez, J., Shparlinski, I.: Predicting nonlinear pseudorandom number generators. Math. Comput. 74, 1471\u20131494 (2005)","journal-title":"Math. Comput."},{"key":"535_CR5","doi-asserted-by":"crossref","unstructured":"Blake, I., Seroussi, G., Smart, N.: Elliptic curves in cryptography. London Math. Soc., Lecture Note Series, vol. 265. Cambridge Univ Press (1999)","DOI":"10.1017\/CBO9781107360211"},{"key":"535_CR6","unstructured":"Bloemer, J., May, A.: A tool kit for Finding small roots of Bivariate Polynomial over the Integers. Advances in Cryptology-Crypt. LNCS 2729, pp. 27\u201343. Springer (2003)"},{"key":"535_CR7","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1145\/58562.59305","volume":"36","author":"J Boyar","year":"1989","unstructured":"Boyar, J.: Inferring sequences produced by pseudo-random number generators. J. ACM 36, 129\u2013141 (1989)","journal-title":"J. ACM"},{"key":"535_CR8","unstructured":"Brickell, E., Odlyzko, A.M.: Cryptanalysis: A survey of recent results. Contemp. cryptology, pp. 501\u2013540. IEEE Press, NY (1992)"},{"issue":"4","key":"535_CR9","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s001459900030","volume":"10","author":"D Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Small solutions to polynomial equations and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233\u2013260 (1997)","journal-title":"J. Cryptol."},{"key":"535_CR10","doi-asserted-by":"crossref","unstructured":"Coppersmith, D.: Finding a Small Root of a Bivariate Integer Equations; Factoring with High Bits Known\u2019. In: Maurer, U. (ed.) Proc. EUROCRYPT-96, LNCS 1070,155\u2013156. Springer, Berlin (1996)","DOI":"10.1007\/3-540-68339-9_16"},{"key":"535_CR11","doi-asserted-by":"crossref","unstructured":"Coron, J. S.: Finding small roots of Bivariate Integer Polynomial Equations Revisted. Proc. Advances in Cryptology- Eurocrypt\u201904, LNCS, 3027, pp. 492\u2013505. Springer (2004)","DOI":"10.1007\/978-3-540-24676-3_29"},{"key":"535_CR12","doi-asserted-by":"crossref","unstructured":"El Mahassni, E., Shparlinski, I.: On the Uniformity of Distribution of Congruential Generators over Elliptic Curves. Proc. Intern. Conf. on Sequences and Their Applications, 257\u2013264 Bergen 2001. Springer, London (2002)","DOI":"10.1007\/978-1-4471-0673-9_19"},{"key":"535_CR13","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1137\/0217016","volume":"17","author":"A Frieze","year":"1988","unstructured":"Frieze, A., H\u00e5stad, J., Kannan, R., Lagarias J. C., Shamir, A.: Reconstructing truncated integer variables satisfying linear congruences. SIAM J. Comp. 17, 262\u2013280 (1988)","journal-title":"SIAM J. Comp."},{"key":"535_CR14","doi-asserted-by":"crossref","unstructured":"Gutierrez, J.: Reconstructing Points of Superelliptic Curves over a Prime Finite Field, Preprint. University of Cantabria (2021)","DOI":"10.3934\/amc.2022022"},{"issue":"12","key":"535_CR15","doi-asserted-by":"publisher","first-page":"5518","DOI":"10.1109\/TIT.2006.885451","volume":"52","author":"D Gomez-Perez","year":"2006","unstructured":"Gomez-Perez, D., Gutierrez, J., ibeas, A.: Attacking the Pollard Generator. IEEE. Trans. Inf. Theory. 52(12), 5518\u20135523 (2006)","journal-title":"IEEE. Trans. Inf. Theory."},{"issue":"290","key":"535_CR16","doi-asserted-by":"publisher","first-page":"2953","DOI":"10.1090\/S0025-5718-2014-02808-1","volume":"83","author":"D Gomez-Perez","year":"2014","unstructured":"Gomez-Perez, D., Gutierrez, J.: Recovering zeros of polynomials modulo a prime\u2019. Math. Comput. 83(290), 2953\u20132965 (2014)","journal-title":"Math. Comput."},{"key":"535_CR17","doi-asserted-by":"crossref","unstructured":"Gong, G., Berson, T., Stinson, D.: Elliptic Curve Pseudorandom Sequence Generators. Lect. Notes in Comp. Sci., vol. 1758, pp. 34\u201349. Springer, Berlin (2000)","DOI":"10.1007\/3-540-46513-8_3"},{"key":"535_CR18","doi-asserted-by":"crossref","unstructured":"Gong, G., Lam, C.: Linear recursive sequences over elliptic curves. Proc. Intern. Conf. on Sequences and their Applications, Bergen 2001, pp. 182-196. Springer, London (2002)","DOI":"10.1007\/978-1-4471-0673-9_13"},{"key":"535_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1993)"},{"issue":"2","key":"535_CR20","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s10623-007-9112-3","volume":"45","author":"J Gutierrez","year":"2007","unstructured":"Gutierrez, J., Ibeas, A.: Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits. Des. Codes Cryptogr. 45(2), 199\u2013212 (2007)","journal-title":"Des. Codes Cryptogr."},{"key":"535_CR21","unstructured":"Hallgren, S.: Linear congruential generators over elliptic curves. Preprint CS-94-143, pp. 1\u201310. Dept. of Comp. Sci. Cornegie Mellon University (1994)"},{"key":"535_CR22","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s10623-003-6153-0","volume":"35","author":"F Hess","year":"2005","unstructured":"Hess, F., Shparlinski, I.: On the linear complexity and multidimensional distribution of congruential generators over elliptic curves. Des. Codes Cryptogr. 35, 111\u2013117 (2005)","journal-title":"Des. Codes Cryptogr."},{"key":"535_CR23","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s001459900042","volume":"11","author":"A Joux","year":"1998","unstructured":"Joux, A., Stern, J.: Lattice reduction: a toolbox for the cryptanalyst. J. Cryptol. 11, 161\u2013185 (1998)","journal-title":"J. Cryptol."},{"key":"535_CR24","doi-asserted-by":"crossref","unstructured":"Jochemz, E., May, A.: A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants Advances in Cryptology (Asiacrypt 2006), Lecture Notes in Computer Science. Springer (2006)","DOI":"10.1007\/11935230_18"},{"key":"535_CR25","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12, 415\u2013440 (1987)","journal-title":"Math. Oper. Res."},{"key":"535_CR26","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1109\/TIT.1985.1056997","volume":"31","author":"D Knuth","year":"1985","unstructured":"Knuth, D.: Deciphering a linear congruential encryption. IEEE Trans. Inf. Theory. 31, 49\u201352 (1985)","journal-title":"IEEE Trans. Inf. Theory."},{"key":"535_CR27","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1016\/0196-6774(92)90054-G","volume":"13","author":"H Krawczyk","year":"1992","unstructured":"Krawczyk, H.: How to predict congruential generators. J. Algorithm. 13, 527\u2013545 (1992)","journal-title":"J. Algorithm."},{"key":"535_CR28","doi-asserted-by":"crossref","unstructured":"Lagarias, J.: Pseudorandom number generators in cryptography and number theory, vol. 42, pp. 115\u2013143. Proc. Symp. in Appl. Math. Amer. Math. Soc., Providence (1990)","DOI":"10.1090\/psapm\/042\/1095554"},{"key":"535_CR29","doi-asserted-by":"publisher","first-page":"338","DOI":"10.4153\/CJM-2005-015-8","volume":"57","author":"T Lange","year":"2005","unstructured":"Lange, T., Shparlinski, I.: Certain exponential sums and random walks on elliptic curves. Canad. J. Math. 57, 338\u2013350 (2005)","journal-title":"Canad. J. Math."},{"key":"535_CR30","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A Lenstra","year":"1982","unstructured":"Lenstra, A., Lenstra, H., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Annalen. 261, 515\u2013534 (1982)","journal-title":"Math. Annalen."},{"key":"535_CR31","doi-asserted-by":"crossref","unstructured":"Mefenza, T.: Inferring sequences produced by a linear congruential generator on elliptic curves using coppersmith\u2019s methods. COCOON 2016 LNCS, vol. 9797, pp .293\u2013304 (2016)","DOI":"10.1007\/978-3-319-42634-1_24"},{"key":"535_CR32","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.tcs.2020.04.025","volume":"280","author":"T Mefenza","year":"2020","unstructured":"Mefenza, T., Vergnaud, D.: Inferring sequences produced by a elliptic Curves generators y using Coppersmith\u2019s methods. Theor. Comput. Sci. 280, 20\u201342 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"535_CR33","unstructured":"Meidl, W., Winterhof, A.: Linear Complexity of sequences and multisequences. , pp. 324\u2013334. Handbook of Finite Fields, CRC Press, Taylor and Francis, Group. edits G. Mullen and D. Panario (2013)"},{"issue":"3-4","key":"535_CR34","first-page":"301","volume":"114","author":"L M\u00e9rai","year":"2012","unstructured":"M\u00e9rai, L.: Remarks on pseudorandom binary sequences over elliptic curves. Fund. Inf. 114(3-4), 301\u2013308 (2012)","journal-title":"Fund. Inf."},{"issue":"3","key":"535_CR35","first-page":"193","volume":"28","author":"L M\u00e9rai","year":"2017","unstructured":"M\u00e9rai, L.: Predicting the elliptic curve congruential generator. Applicable Algebra in Engineering. Commun. Comput. 28(3), 193\u2013203 (2017)","journal-title":"Commun. Comput."},{"key":"535_CR36","unstructured":"Naor, M., Reingold, O.: Number theoretic constructions of efficient pseudo-random functions. Proc 38th IEEE Symp. on Found. of Comp. Sci., pp. 458\u2013467. IEEE (1997)"},{"key":"535_CR37","unstructured":"Niederreiter, H.: Design and Analysis of Nonlinear Pseudorandom Number Generators. In: Schueller, G.I., Spanos, P. D. (eds.) Monte Carlo Simulation, pp 3\u20139. A. Balkema Publishers, Rotterdam (2001)"},{"key":"535_CR38","doi-asserted-by":"crossref","unstructured":"Shparlinski, I.: Cryptographic applications of analytic number theory. Birkhauser (2003)","DOI":"10.1007\/978-3-0348-8037-4"},{"key":"535_CR39","doi-asserted-by":"crossref","unstructured":"Shparlinski, I.: Orders of points on elliptic curves. Affine Algebraic Geometry. Amer. Math. Soc., pp. 245\u2013252 (2005)","DOI":"10.1090\/conm\/369\/06815"},{"key":"535_CR40","doi-asserted-by":"crossref","unstructured":"Shparlinski, I.: Pseudorandom Points on Elliptic Curves over Finite Fields. Recent trends in Cryptography. Contemporary Mathematics, v.477, Amer.Math. Soc., pp. 121\u2013141 (2009)","DOI":"10.1090\/conm\/477\/09305"},{"key":"535_CR41","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s002000000023","volume":"11","author":"I Shparlinski","year":"2000","unstructured":"Shparlinski, I: On the Naor-Reingold pseudo-random function from elliptic curves. Appl. Algebra Engin. Commun. Comput. 11, 27\u201334 (2000)","journal-title":"Appl. Algebra Engin. Commun. Comput."},{"key":"535_CR42","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1023\/A:1011223204345","volume":"24","author":"I Shparlinski","year":"2001","unstructured":"Shparlinski, I., Silverman, J.: On the linear complexity of the Naor-Reingold pseudorandom function from elliptic curves. Des. Codes Cryptogr. 24, 279\u2013289 (2001)","journal-title":"Des. Codes Cryptogr."},{"key":"535_CR43","volume-title":"The Arithmetic of Elliptic Curves","author":"J Silverman","year":"1995","unstructured":"Silverman, J.: The Arithmetic of Elliptic Curves. Springer, Berlin (1995)"},{"key":"535_CR44","doi-asserted-by":"crossref","unstructured":"Sun, H., Zhu, X., Zheng, Q.: Predicting truncated multiple recursive generators with unknown parameters. Des. Codes Cryptogr., pp. 1\u201320 (2020)","DOI":"10.1007\/s10623-020-00729-8"},{"key":"535_CR45","doi-asserted-by":"crossref","unstructured":"Winterhof, A.: Recent results on recursive nonlinear pseudorandom number generators. (Invited Paper). SETA 2010: 113\u2013124 (2010)","DOI":"10.1007\/978-3-642-15874-2_9"}],"container-title":["Cryptography and Communications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-021-00535-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12095-021-00535-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-021-00535-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T10:10:38Z","timestamp":1651572638000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12095-021-00535-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,12]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["535"],"URL":"https:\/\/doi.org\/10.1007\/s12095-021-00535-6","relation":{},"ISSN":["1936-2447","1936-2455"],"issn-type":[{"value":"1936-2447","type":"print"},{"value":"1936-2455","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,12]]},"assertion":[{"value":"19 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}