There is an elaborate discussion on the breaking of TLCG on the link below, where they show how to break the generator with known parameters given the most significant bits. Problem with LLL reduction on truncated LCG schemes

I tried to apply the same principles when given the least significant bits but with no success. On the paper by Frieze et al they discuss it briefly and mention substituting *x = 2s0*x(1) + x(2)* that helps a little bit but I cant figure out what the value of s0 is supposed to be. Is the anyone who can help.?

  • 1
    $\begingroup$ Could you state the givens in the problem at hand? Is the modulus prime, a power of two, other? $\endgroup$ – fgrieu Apr 28 '18 at 12:55

According to the paper Freize et al, for the most significant bit case which is discussed at length in the link,the modulus M must be odd, the addend I assume can be any number between 1 and the modulus, and the increment must be zero. So given:

a*x(i) + b ~ mod M
M is odd 
0 > a < M
b = 0

Because both a and $M$ are known n we obtain high order bits y(i). Then $x = y + z$ where $y$ is the high order bits $n$, $z$ is the lower order bits.

Lx ~ 0 mod M
Taking B the reduced basis of yields.
Bx ~ 0 mod M
Substituting x = y + z gives
B x + By ~ 0 mod M which yields the equation
Bx + By = km for an unknown vector k of integers.

From this point, its easy to find the lower order bits $z$. (see the link above)

In the case where we are give the lower significant bits $z$ instead of the higher bits $y$, the paper suggests substituting $x = 2(s0)* y + z$. And they talk about finding the inverse of $2(s0) \pmod M$ which is guaranteed to exist since M is odd. But that's where I get completely lost.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.