Given a basis $\{v_1,\dots,v_k\}$ for a $q$-ary lattice $L$ in ${\mathbb Z}_q^n$, is there an efficient (deterministic/randomized) way to find a point in $L$ with all non-zero components, or decide that it does not exist?
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This looks like a hard problem in general, although the lattice viewpoint may not be the right one to look at it. Basically, this is a coding theory question: you are asking about the existence of a full-weight codeword in a linear code over $\mathbb{F}_q$ (and if it does exist, how to find it efficiently). The question has been asked on MathOverflow a few months ago, with no answer so far, but some of the cited references may be useful.
Aside from the fact that this is a question about Hamming weights, I say the lattice viewpoint doesn't seem quite right for at least two reasons.
On the one hand, the problem can be seen as an instance of bounded distance decoding: it asks to find a lattice point within $\ell^\infty$-norm $<q/2$ of $(q/2,\dots,q/2)$. This type of problem is usually hard.
On the other hand, for $q$-ary lattices that normally occur in lattice-based cryptography, simply sampling a random lattice point is expected to solve the problem with good probability. This is because we typically have $q$ much larger than $n$. A random element of $\mathbb{F}_q^n$ has all non-zero coordinates with probability $(1-1/q)^n$ which is close to $1$ in that setting; thus, if the points of $L$ look “roughly random” (which is usually the case, and often an explicit assumption, in lattice-based crypto), you expect a very large fraction of them to have all non-zero coordinates. Therefore, simply sampling a random one should work. An exception is of course the case when the component at some fixed index $i$ is zero for all lattice points, but this is easy to test for by inspection of the basis or by computing the dual lattice.
EDIT: after thinking about the problem some more, I suspect that it is probably NP-hard for any fixed $q\geq 3$.
