Reconstructing Truncated Integer Variables Satisfying Linear Congruences

DOI10.1137/0217016MaRDI QIDQ3800123zbMATH OpenOpenAlexWikidataFDO

Authors Jeffrey C. Lagarias, Adi Shamir, Alan Frieze, Johan Hastad, R. 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

algorithmapplications in cryptographybreaking of simplest version of Blum's protocol for exchanging secretscomputational number theorylattice basis reduction algorithmpolynomial timeprediction of linear congruential generators whose outputs are truncatedreconstruction of variablessmall integer solutionssystems of linear congruences

Mathematics Subject Classification ID

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

Recommendations

• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits
• Solving Simultaneous Modular Equations of Low Degree
• Chinese remaindering with multiplicative noise
• scientific article; zbMATH DE number 4212179

Cited in

(30)

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

This page was built for publication: Reconstructing Truncated Integer Variables Satisfying Linear Congruences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3800123)