SVP (shortest vector problem) is equivalent to SIVP (shortest independent vectors problem) in ring lattice (ideal lattice). How to prove this? Could someone explain it to me? Thanks!


Consider the ring $R = \mathbb{Z}[x]/(f(x))$ for $f(x)$ an irreducible monic polynomial of degree $n$. Fix a basis $\{1,x,\dots,x^{n-1}\}$, and define the following transformation: $$L(x^i) = x^{i+1}$$ Extend this transformation to all of $R$ via linearity. Cayley-Hamilton theorem [1] states that the characteristic polynomial $p(t) = \det(L - tI)$ is such that: $$p(L) = 0$$ One can explicitly compute the square matrix corresponding to $L$ (it is the companion matrix of $f(x)$), and it is known that:

  • The characteristic polynomial of $L$
  • The minimal polynomial of $L$
  • $f(x)$

Are all identical. It follows that $f(L) = 0$, and this is the smallest polynomial $f(x)$ for which this holds, so among other things $\{1,x,\dots,x^{n-1}\}$ are linearly independent over $R$.

Now let $v(x)\in R$ be any vector (including a candidate "shortest vector"). We have that $\{v(x), xv(x), \dots, x^{n-1}v(x)\}$ are linearly independent over $R$. This is because if there were some linear relation between them: $$\sum_i a_iv(x)x^i = 0\implies v(x)\sum_i a_ix^i = 0\implies \sum_i a_i x^i = 0$$ Contradicting the linear independence. As $\| x^i v(x)\|$ are all the same, we've exhibited a basis of vectors of the same norm. So finding one short vector is enough to find all $n$ short vectors.

[1] Technically we need to make sure that Cayley-Hamiltonian holds over modules over general rings. Fortunately it is known to hold for commutative rings, so we're fine.

  • 4
    $\begingroup$ It’s not true that $\| x^i v(x) \|$ are all the same (in general), because there is “wraparound” modulo $f$, which can affect the norm. For certain $f$ it is true, but in general, the choice of $f$ affects the loss factor between the SVP and SIVP problems. $\endgroup$ Apr 17 '20 at 22:20

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.