World's most popular travel blog for travel bloggers.

# How broken is LCG in the case of partial output?

, ,
Problem Detail:

Suppose we have a linear congruential generator defined by \$X_{n+1} = (a X_n + c) \mod 2^n\$ where \$a, c, n\$ are all known and we would like to determine the initial value \$X_0\$. However, if we can only see the \$k\$ high-order bits of each of the \$X_i\$ for \$i \geq 0\$, the best algorithm I know of is a brute force which tries \$O(2^{n-2k})\$ possibilities, and this is exponential in \$n\$.

Compare this to the Mersenne Twister, whose initial state can be computed in polynomial time given only the high-order bits of each output (it reduces to solving a system of \$n\$ equations in \$n\$ unknowns). Is there a better algorithm out there which can solve for the initial state of an LCG given only the high-order bits of each output, and if not, is LCG actually broken?

###### Asked By : Sam Fingeret

Yes, there are techniques based on lattice reduction that are faster than brute force. See, e.g., http://crypto.stackexchange.com/a/20714/351, especially the first 3 papers cited there.

One can also use meet-in-the-middle techniques to get the running time down to \$O(2^{(n - k)/2})\$ if \$k \ge n/2\$: see http://crypto.stackexchange.com/a/10609/351.