Reconstructing Truncated Integer Variables Satisfying Linear Congruences

DOI10.1137/0217016zbMath0654.10006OpenAlexW2080017147WikidataQ56959247 ScholiaQ56959247MaRDI QIDQ3800123

Jeffrey C. Lagarias, Adi Shamir, Alan M. Frieze, Johan T. Håstad, Ravindran Kannan

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0217016

zbMATH Keywords

algorithmpolynomial timecomputational number theorysystems of linear congruenceslattice basis reduction algorithmsmall integer solutionsreconstruction of variablesapplications in cryptographybreaking of simplest version of Blum's protocol for exchanging secretsprediction of linear congruential generators whose outputs are truncated

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Congruences; primitive roots; residue systems (11A07)

Related Items

Meta-heuristic approaches to solve shortest lattice vector problem, Distribution of Hermite's constant and the shortest vector in lattices of dimension two, Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes, Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation, Quantum period reconstruction of approximate sequences, Pseudorandom numbers and hash functions from iterations of multivariate polynomials, Attacks on pseudo random number generators hiding a linear structure, Recovering zeros of polynomials modulo a prime, Inferring sequences produced by a linear congruential generator missing low-order bits, Predicting truncated multiple recursive generators with unknown parameters, Attacking the linear congruential generator on elliptic curves via lattice techniques, Reconstructing points of superelliptic curves over a prime finite field, On elliptic curve $L$-functions integrated encryption scheme, Predicting masked linear pseudorandom number generators over finite fields, An improved method for predicting truncated multiple recursive generators with unknown parameters, A new privacy homomorphism and applications, Binary sequences derived from ML-sequences over rings. I: Periods and minimal polynomials, La réduction des réseaux. Autour de l'algorithme de Lenstra, Lenstra, Lovász, A natural lattice basis problem with applications, On the degree growth in some polynomial dynamical systems and nonlinear pseudorandom number generators, Predicting nonlinear pseudorandom number generators, On pseudorandom numbers from multivariate polynomial systems, Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits, Estimates of lengths of shortest nonzero vectors in some lattices. II, Estimates of lengths of shortest nonzero vectors in some lattices. I, On the linear complexity and multidimensional distribution of congruential generators over elliptic curves, JEROBOAM, A generator of pseudo-random numbers sequences with a very long period