1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

  1. 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.

  2. 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.