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

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?

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 https://crypto.stackexchange.com/a/10609/351.
• The meet in the middle attack is flawed in the case that $k < n/2$. The attack assumes that we can compute $X_0$ based on the high order bits of $X_0$ and $X_1$ only, but there are only $2k$ bits here, so we would be left with $2^{n - 2k}$ possibilities and there is no improvement. I do not understand how the lattice reduction techniques are relevant here, as far as I can tell they aim to solve the different problem where $a, c, n$ are unknown but where the full outputs are known. – Sam Fingeret Feb 16 '16 at 23:48
• @SamFingeret, thanks for the feedback. I've updated my answer accordingly. On lattice reduction: I think you gave up too quickly. See the updated link, especially the 3 papers cited there. I think they do solve exactly your problem -- the papers are clear that they are talking about the case of observing truncated outputs (the full outputs are not known). For the meet-in-the-middle attack: I've revised my answer accordingly. Thank you for the correction and for spotting my error. It wouldn't surprise me if we could relax the $k \ge n/2$ condition, e.g., by considering $X_0,X_1,X_2$. – D.W. Feb 17 '16 at 2:18
• For instance, would it help to write $X_1= c 2^{n-k} + 2^{(n-k)/2} d + e$ and then write $X_0 = \text{known} + \text{known} \times d + \text{known} \times e$ and $X_2 = \text{known} + \text{known} \times d + \text{known} \times e$? We could look for a match between the pair $(X_0 - \text{known} \times d, X_2 - \text{known} \times d)$ and the pair $(\text{known} + \text{known} \times e, \text{known} + \text{known} \times e)$. – D.W. Feb 17 '16 at 2:22