0
$\begingroup$

I'm interesting in the lattice problems (the one used in the post quantum crypto), especially the shortest vector problem. I'm trying to understand why it is hard by finding an example, but I can't find in dimension 2 a lattice and a base in which finding the shortest vector is not trivial (I'm always able to find the shortest vector by doing something like two subtractions).

For example, let's consider this "nice" (nearly orthogonal) base:

enter image description here

I can build from this base a new base (C,D) (in read):

enter image description here

which is less orthogonal. However, I can recover (A, B) in only two steps:

B = D-C
A = C-B

All the others based I can found are in the same idea: add to (C,D) a given number n of the B vector, but all of these bases allow me to recover the initial base in a small number of steps (basically a greedy algorithm seems to be able to find it by subtracting the two vectors, and then use this new vector to find the other vector by doing n subtracts).

Does anyone know a way to generate non trivial bases such that finding the original base would be more complicated than just doing two substractions?

Thank you!

EDIT

I react here to the solution proposed by Will Jagy (thank you for your answer). If I try the basis $v_1 = (15,-7,-7)$, $v_2 = (-7,15,-7)$ and $v_3 = (-7,-7,15)$, then I can find in 6 operations the shortest vector $v_m = (1,1,1)$ (thank you to the great 3D tools of Geogebra). So it's not amazing but you can tell me "you were lucky", or "it's because it's in a small dimension". Well the problem is that this vector is even given by the Hermite decomposition which is computable in polynomial time (here using the great sagemath to compute it):

>>> matrix(ZZ,3, [15,-7,-7,-7,15,-7,-7,-7,15]).hermite_form()
[ 1  1  1]
[ 0 22  0]
[ 0  0 22]

(the vectors are read line by line)

I tried then to plot the lattice using blender:

import bpy
def main():
    m = 3
    v1 = [15,-7,-7]
    v2 = [-7, 15, -7]
    v3 = [-7,-7,15]
    for i in range(-m,m):
        for j in range(-m,m):
            for k in range(-m,m):
                l = [i*t1+j*t2+k*t3 for (t1,t2,t3) in zip(v1,v2,v3)]
                bpy.ops.mesh.primitive_uv_sphere_add(size=0.3, location=l)

main()

in read I put the base vectors, in green the shortest vector, and in grey you have some others vectors of the lattice:

enter image description here

enter image description here

Wouldn't it be possible to also have a basis where the Hermite form is also bad?

$\endgroup$
3
  • $\begingroup$ the matrix $$ \left( \begin{array}{rrr} 15 & -7 & -7 \\ -7 & 15 & -7 \\ -7 & -7 & 15 \end{array} \right) $$ does not show a basis. Note that it is symmetric. It is half the Hessian matrix of second partial derivatives of the quadratic form. It is usually called the Gram matrix of the form $$ 15 x^2 + 15 y^2 + 15 z^2 - 14 yz - 14 zx - 14 xy $$ $\endgroup$
    – Will Jagy
    Commented Mar 17, 2017 at 17:57
  • 1
    $\begingroup$ Lattice problems are all easy in low dimensions - the hardness for the use in cryptography comes from the high dimension. So in crypto you're not talking about a 2D or 3D lattice but some beast that lives in say 1000 dimensions. Examples can for instance be found on the "SVP challenge" website, and here's one in dimension 40 (rows being vectors): latticechallenge.org/svp-challenge/download/challenges/… $\endgroup$
    – TMM
    Commented Aug 6, 2017 at 1:41
  • $\begingroup$ Note that also such 40-dimensional lattices are considered "easy" now with tools like LLL, BKZ, enumeration et cetera. The highest-dimensional "random" lattice for which SVP has been solved* is currently a 150-dimensional lattice. $\endgroup$
    – TMM
    Commented Aug 6, 2017 at 1:43

1 Answer 1

Reset to default
0
$\begingroup$

with dimension two, finding the shortest vector is Gauss reduction, completely algorithmic and about the same speed as finding the gcd of two numbers, similar problems.

Find the smallest integer for $x,y,z$ integers not all zero, of $$ 15 x^2 + 15 y^2 + 15 z^2 - 14 yz - 14 zx - 14 xy $$ Still not hard. The problem begins to get some edge in five or more variables.

$$ C^T = \left( \begin{array}{rrr} \sqrt{15} & 0 & 0 \\ -\frac{7}{\sqrt{15}} & \frac{4 \sqrt{11}}{\sqrt{15}} & 0 \\ -\frac{7}{\sqrt{15}} & -\frac{7 \sqrt{11}}{2\sqrt{15}} & \frac{ \sqrt{11}}{2} \end{array} \right) $$ $$ C = \left( \begin{array}{rrr} \sqrt{15} & -\frac{7}{\sqrt{15}} & -\frac{7}{\sqrt{15}} \\ 0 & \frac{4 \sqrt{11}}{\sqrt{15}} & -\frac{7 \sqrt{11}}{2\sqrt{15}} \\ 0 & 0 & \frac{ \sqrt{11}}{2} \end{array} \right) $$ $$ C^T C = \left( \begin{array}{rrr} 15 & -7 & -7 \\ -7 & 15 & -7 \\ -7 & -7 & 15 \end{array} \right) $$

The square roots are a fairly good reason to look for a basis in larger dimension

$$ \left( \begin{array}{rrrrrr} 2 & 2& 2& 1& 1& 1\\ 1 & -2 & -1 & -2 & -2 & 1 \\ -2 & -1 & -1& 1& 2 & -2 \end{array} \right) \left( \begin{array}{rrr} 2 &1 & -2\\ 2 &-2& -1\\ 2 &-1& -1\\ 1 &-2& 1\\ 1 &-2& 2\\ 1 &1& -2 \end{array} \right)= \left( \begin{array}{rrr} 15 &-7& -7 \\ -7 &15& -7 \\ -7 &-7& 15 \end{array} \right) $$

Had not planned on this part. A basis corresponding to this three variable form is some version of a Cholesky decomposition, that is $C^T C = H.$ This is not going to be possible with integer (or rational) entries, but square roots will suffice.

$\endgroup$
6
  • $\begingroup$ Thank you for your answer, but I'm not sure to understand how you do the translation from this multiple variable polynomial P into a basis of a lattice, could you elaborate on this please ? $\endgroup$
    – tobiasBora
    Commented Mar 15, 2017 at 23:52
  • 1
    $\begingroup$ @tobiasBora, maybe this will be better: take a basis of two vectors in the plane $a = (73, 100)$ and $b = (100, 137).$ Find the shortest vector, indeed a nice new short basis. $\endgroup$
    – Will Jagy
    Commented Mar 16, 2017 at 0:01
  • $\begingroup$ It is an interesting example indeed. After it's still not too difficult (I found the basis (0,1), (1,0) after 13 steps is it that ?), but I think that it's because the dimension is too small, as explained in your answer. So I'm still interested by your 3D example :D And by the way, how can you find a difficult basis, is there any algorithm for that? I heard about the Hermitian normal form, but I think it's not the only way to get a difficult basis. $\endgroup$
    – tobiasBora
    Commented Mar 16, 2017 at 0:30
  • $\begingroup$ @tobiasBora I think you can answer the part about finding a "difficult" basis for yourself. Find integers $e,f,g,h$ so that $e(73,100) + f(100,137) = (1,0),$ then $g(73,100) + h(100,137) = (0,1).$ The process of finding the short basis can be extended by a certain type of bookkeeping so that $e,f,g,h$ are produced algorithmically. But guessing is also fine for the investigation aspect of this. $\endgroup$
    – Will Jagy
    Commented Mar 16, 2017 at 0:44
  • $\begingroup$ Yes sure. And what about your 3D example? How do you convert this polynomial into a basis? $\endgroup$
    – tobiasBora
    Commented Mar 16, 2017 at 11:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .