World's most popular travel blog for travel bloggers.

How broken is LCG in the case of partial output?

, , No Comments
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
Answered By : D.W.

Yes, there are techniques based on lattice reduction that are faster than brute force. See, e.g.,, 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

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback