7
$\begingroup$

What is the Lenstra–Lenstra–Lovász lattice basis reduction algorithm about?

How is it applied to solve for $x\pmod m$ a system of modular inequalities $(u_i\,x+v_i\bmod m)<w$ for $0\le i<n$?

I'm aware of this related question, but would like something introductory and detached from a Linear Congruential Generator. I understand the notion of basis of a vector space, but would not recognize a lattice or lattice basis should I walk by one.


If a numerical illustration is needed, perhaps consider the PRNG based on a LCG truncated to it's $k$ high bits, modulus $m=2^{k\,n}$, multiplier $a=8\left\lfloor m\,\pi/64\right\rfloor+5$, addend $b=1$, seed term $x_0=x\bmod m$, recurrence $x_{i+1}=a\,x_i+b\bmod m$, output $y_i=\left\lfloor 2^k\,x_i/m\right\rfloor$.
That can be expressed as $(u_i\,x+v_i\bmod m)<w$ as in the question for $w=m/2^k$, $u_i=a^i\bmod m$, $v_0=-w\,y_0\bmod m$, $v_{i+1}=a\,(v_i+w\,y_i)+b-w\,y_{i+1}\bmod n$.

$\endgroup$
2
  • 1
    $\begingroup$ I'm not sure that your example, leaking only 1 bit per iteration, is solvable with lattice methods. Not easily, at least. $\endgroup$ – Samuel Neves Nov 28 '20 at 16:07
  • $\begingroup$ @Samuel Neves: thanks for the advice. I have introduced an additional parameter $k$ in the reference problem, which allows for example a modulus $m=2^{64}$, and $n=4$ outputs each $k=16$ bits. Also I toned down my ignorance to a more realistic level. $\endgroup$ – fgrieu Nov 28 '20 at 16:38
10
$\begingroup$

The short answer is that LLL (or more generally, lattice reduction methods) is useful when you can convert your problem into finding a small linear combination of known vectors.

Let's take your example and make it concrete. Let $m = 2^{64}$, $a = 7244019458077122845$, $b=1$, and the we have a generator that outputs the upper 16 bits of the state at each iteration:

sage: k = 16
sage: n = 4
sage: m = 2^(n*k)
sage: a = 8 * floor(m*pi/64) + 5
sage: b = 1
sage: x0 = 5183095426420329486 # randint(0, m)
sage: x = x0
sage: 
sage: l = 6
sage: 
sage: X = []
sage: Y = []
sage: Z = []
sage: for i in range(l): 
sage:   x = (a*x + b) % m
sage:   X.append(x)
sage:   Y.append( x - x % 2^(n*k - k) )
sage:   Z.append( x % 2^(n*k - k) )

Here we have 6 outputs; that'll be enough, as we'll see later. The vector $\mathbf{X}$ represents the full state at each iteration; the vector $\mathbf{Y}$ represents what we obtain from the generator (conveniently multiplied by $2^{48}$), and the vector $\mathbf{Z}$ is the information we are missing. Obviously, $\mathbf{X} = \mathbf{Y} + \mathbf{Z}$.

Now we can indeed turn this into a less recursive function. We can represent each element of $\mathbf{X}$ as $$ X_i = a^i\cdot x_0 + b\cdot \sum_j^i a^j \bmod m\,, $$ where $x_0$ here is the seed we are looking for.

sage: A = [ power_mod(a, i, m) for i in range(1, l+1) ]
sage: B = [ b * sum([ power_mod(a, j, m) for j in range(i) ]) % m for i in range(1, l+1) ]
sage: assert( X[i] == (A[i]*x0 + B[i]) % m )

What we have now is a vector relation: $$ x_0\cdot \mathbf{A} + \mathbf{B} = \mathbf{Y} + \mathbf{Z} \pmod{m} \,. $$ We can move the $\mathbf{B}$ vector to the other side: $$ x_0\cdot \mathbf{A} = \mathbf{Y} + \mathbf{Z} - \mathbf{B} \pmod{m} \,. $$ Because we do not know $\mathbf{Z}$, we can't solve this, of course. But because $\mathbf{Z}$ is relatively small—made up of only 48-bit coefficients—we can do something else. All of the possible elements on the left side can be represented as combinations of the rows of the following matrix: $$ \begin{pmatrix} m & 0 & \dots & 0 \\ 0 & m & \dots & 0 \\ \dots & \dots & \dots & \dots \\ 0 & 0 & \dots & m \\ A_0 & A_1 & \dots & A_{l-1} \end{pmatrix} $$ Every vector of the lattice spanned by these rows is given by $(v_0\cdot m + v_{l-1}\cdot A_0, v_1\cdot m + v_{l-1}\cdot A_1,$ $\dots$ $, v_{l-1}\cdot m + v_l \cdot A_{l-1})$, for some integer vector $(v_0, v_1, \dots, v_l)$. Note that the multiplications by $m$ disappear when reduced modulo $m$; they are there purely to represent the modular relation over the integers (seeing that $x \bmod m = x + m\cdot k$ for any integer $k$). By definition we know that there is some point in this lattice that is equal to $\mathbf{Y} + \mathbf{Z} - \mathbf{B} \bmod m$. Our hope is that we can find some vector in this lattice that will be in the vicinity of $\mathbf{Y} - \mathbf{B}$; that is, even if we don't have $\mathbf{Z}$, if $\mathbf{Z}$ is small enough we may be able to find $\mathbf{Y} + \mathbf{Z} - \mathbf{B}$ anyway. Let's try:

sage: t = vector([ ZZ( (Y[i] - B[i]) % m ) for i in range(l) ])
sage: L = diagonal_matrix(ZZ, [m] * l, sparse=False)
sage: L = L.insert_row(l, A)
sage: from sage.modules.free_module_integer import IntegerLattice
sage: from fpylll import CVP, IntegerMatrix
sage: v = vector( CVP.closest_vector(IntegerMatrix.from_matrix(IntegerLattice(L).basis_matrix()), t) )
sage: v
(13248830508827011990, 14756727165374399998, 10872974672493767622, 3944908843490556782, 9056698072341178742, 12371060381645645918)
sage: (vector(Z) + vector(Y) - vector(B)) % m
(13248830508827011990, 14756727165374399998, 10872974672493767622, 3944908843490556782, 9056698072341178742, 12371060381645645918)

It works! (Don't pay much mind to how this vector is found; let's pretend it's a closest vector blackbox).

Having this vector it is now straightforward to obtain $x_0$. We can use linear algebra, for instance:

sage: L.change_ring(Zmod(m)).solve_left(v)
(0, 0, 0, 0, 0, 0, 5183095426420329486)
sage: x0
5183095426420329486

Why does this work? It's complicated. But the basic idea is, if you have a lattice given by a matrix $L$ of rank $n$, its volume is given by the determinant, and the shortest (resp. closest, with some caveats) vector is known to be at most $\sqrt{n} \mathrm{det}(L)^{1/n}$ distance (usually in $L_2$ norm). In our case, that is

sage: (sqrt(L.rank())*IntegerLattice(L).volume()^(1/L.rank())).log(2).n()
53.9751060324574

But our expected distance to $\mathbf{Y} - \mathbf{B}$, i.e., the norm of $\mathbf{Z}$, is shorter than that, having norm approximately $2^{48}$ (since we are missing 48 bits of state):

sage: (t-v).norm().log(2).n()
48.4871956406101

Therefore it is highly likely that the closest vector to $\mathbf{Y} - \mathbf{B}$ is indeed our solution.

This also explains why when you leak too few bits the method stops working: the norm of $\mathbf{Z}$ becomes larger than the norm of the expected closest vectors, so you start getting unrelated vectors as the closest point. If $\mathbf{Z}$ is 63 bits, then your distance is approximately 64 bits long, which is much higher than $2^{53.97}$.

But we haven't used LLL yet. In fact, LLL does not even find closest vectors! However, up to some approximation error (exponential on the dimension), LLL does find very short vectors. If the error is not too large, LLL can serve as a decent replacement to a shortest vector blackbox. So one common approach is to turn closest vector problems, such as this one, into shortest vector problems that LLL can tackle.

One option, which uses LLL internally, would be to use the Babai nearest plane method to find a close vector. But there is a simpler trick, due to Kannan, to (heuristically) embed a closest vector problem into a shortest vector problem. The idea is to extend the lattice such that the closest vector is a short vector in it. Coupled with LLL (or BKZ), we can obtain a solution that way: $$ \begin{pmatrix} m & 0 & \dots & 0 & 0 \\ 0 & m & \dots & 0 & 0\\ \dots & \dots & \dots & \dots & 0 \\ 0 & 0 & \dots & m & 0\\ A_0 & A_1 & \dots & A_{l-1} & 0 \\ Y_0 - B_0 & Y_1 - B_1 & \dots & Y_{l-1} - B_{l-1} & M \end{pmatrix}\,, $$ where $M$ here is an approximation of the expected distance, that is, the norm of $\mathbf{Z}$. Because we expect $\mathbf{Z}$ to be small, the vector $x_0\cdot \mathbf{A} - (\mathbf{Y} - \mathbf{B})$ is expected to be short as well, and hopefully LLL gives us a solution.

sage: t = vector([ ZZ( -(Y[i] - B[i]) % m ) for i in range(l) ])
sage: L = diagonal_matrix(ZZ, [m] * l + [0], sparse=False)
sage: L.set_row(l, A + [0])
sage: L = L.insert_row(l+1, list(t) + [2^(n*k - k)])
sage: L.LLL()
[                 0                  0                  0                  0                  0                  0                  0]
[    84830033144727     99493793228572    193251317565997    195477621437466     41221639930099    247621686570632    281474976710656]
[  -687665523248565   -558678928843390  -2831909104870979    783681348831084   3591271679705919     61017834323238    844424930131968]
[ -1823548220242427   2253638642602902  -3569730745364989   3416755876477276   -751301580596367  -2032834227000110   1407374883553280]
[  7621930640779355   -105157344785070  -3265673334549427   1969120201701820  -1755046640220593  -2112569643194890    844424930131968]
[ -1177023352112110  -3396609545281551    557994199985972  10658623678942411    804267325513190    663710453352693  -7036874417766400]
[  4998293895365537  11389134223649311  -2635952223845275   2485610916234323   4530338313613385   2884351148040487  -8444249301319680]
[  -192992080812070   5962407351033287  11672086573074080   -997631747809227   8935027883752214 -19143574866262125   5910974510923776]
sage: vector(Z)
(84830033144727, 99493793228572, 193251317565997, 195477621437466, 41221639930099, 247621686570632)

The shortest nonzero vector in this lattice is exactly $\mathbf{Z}$ (plus an extra element), the missing information to get us to $\mathbf{Y} + \mathbf{Z} - \mathbf{B}$. We can now solve for $x_0$ as before.

Long story short, if you are able to coax your problem into a question of finding linear combinations that are either short or near some known vector, lattices might be of use. This, of course, does not even begin to scratch the surface of what you can do with lattices. The article by Joux and Stern entitled Lattice Reduction: a Toolbox for the Cryptanalyst is a good—and far more rigorous—introduction to this topic.

$\endgroup$
2
  • 4
    $\begingroup$ Many thanks, that's very much what I hoped for. Unfortunately for your rep, I'll click accept only when I think I have fully grasped it. But at least that's likely to happen, when sadly Joux and Stern have been on my toread list for the past 7 years. $\endgroup$ – fgrieu Nov 29 '20 at 10:13
  • 4
    $\begingroup$ Very useful answer!!! Thanks a lot, @samuel-neves $\endgroup$ – ddddavidee Nov 29 '20 at 15:55

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.