Score:2

What is the fastest way to check whether a given vector is the shortest in a lattice?

us flag

Given a lattice L and a vector $v_1$ claimed to be the shortest, what is the fastest way to check/verify whether $v_1$ is indeed the shortest in the lattice?

Maarten Bodewes avatar
in flag
What part of this is related to cryptography rather than [math.se]? Have you looked at that site?
us flag
<<What part of this is related to cryptography>> Well, for lattice-based cryptography, one claimed advantage is that the hard problem such as the shortest vector problem (SVP) is NP hard, instead of just being NP. NP hard is supposed to be even harder than NP; The integer factorization and discrete logarithm problems are in NP. My original question is about whether SVP may actually be in NP.
cn flag
NP-hard problems are at least as hard as the NP-complete problems. Strictly speaking, calling them harder than NP problems is not correct.
Score:4
ng flag

The standard way that SVP is formalized is such that what you ask isn't really relevant to showing $SVP\in\mathsf{NP}$. The typical formalization of SVP is (for an arbitrary norm $\lVert\cdot\rVert$ on $\mathbb{R}^n$ --- note that the hardness of SVP can depend on the particular choice of norm):

Let $n\in\mathbb{N}$, and $\gamma\in\mathbb{R}_{\geq 0}$. An instance of SVP is a pair $(\Lambda, \gamma)$, where $\Lambda\subseteq\mathbb{R}^n$ is a lattice, and $\gamma$ a constant. We say that an SVP instance $(\Lambda,\gamma)$ is accepting if: $$\min_{v\in\Lambda\setminus\{0\}}\lVert v\rVert \leq\gamma$$ and rejecting otherwise.

In terms of this formulation of the problem, the NP witness to a problem instance $(\Lambda, \gamma)$ is any vector $v\in\Lambda\setminus\{0\}$ such that $\lVert v\rVert \leq \gamma$. These clearly can be efficiently described, and it should also be clear how one can efficiently verify whether $(\Lambda,\gamma)$ is accepting or rejecting, given such a witness.


Of course, your question has a broader interpretation --- can we efficiently determine whether some candidate shortest vector $v$ is "actually" the shortest vector in the lattice? I'm not an expert, but:

  1. I don't believe this is known in the worst case (but am not sure)
  2. In the average case (which is the one everyone cares about), strong enough concentration results on $\lambda_1(\Lambda)$ are known that it doesn't matter.

In particular, for most candidate "hard" distributions over lattices $\Lambda\gets \mathcal{D}$, $\lambda_1(\Lambda)$ is highly concentrated around some known value, so to "check" if some candidate vector $v$ is the shortest in some random lattice $\Lambda$, it suffices to check if $\lVert v\rVert$ is close to the known value of $\mathbb{E}_{\Lambda\gets\mathcal{D}}[\lambda_1(\Lambda)]$. See for example Random Lattices: Theory and Practice, which includes some pointers to relevant mathematical work.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.