4
$\begingroup$

Given $q$ and a matrix $A \in \mathbb{Z}_q^{n \times m}$, the $q$-ary lattice is defined as $$\Lambda(A)=\{x \in \mathbb{Z}^m:Ax=0 \bmod q\} $$ An instance of a q-ary lattice and its short basis is computed in Generating short basis for hard random lattices. Once the short basis $T_A$ for $\Lambda(A)$ is given, computing the short vector $s$ in $\Lambda (A)$ is given in SamplePre algorithm.

Is it possible to find a short basis for $\Lambda(A^T)$, if we are given a short basis of $ \Lambda(A)$?

Basically I want to find the short vector $s^\prime$ such that $A^Ts^\prime=0 \bmod q$.

$\endgroup$
  • $\begingroup$ It is highly unlikely that such a short (nonzero) vector $s’$ exists, for a uniformly random $A$ and typical dimensions $m \gg n$. $\endgroup$ – Chris Peikert Jul 6 '19 at 14:48
2
+25
$\begingroup$

If $n<m$ then for almost all matrices $A$ the columns of $A^T$ will be linearly independent and in that case $\Lambda(A^T)$ is the lattice generated by the basis $qI$ (which is the shortest possible basis for this lattice).

| improve this answer | |
$\endgroup$
  • $\begingroup$ The basis would not be $qI$ because that does not include the columns of $A^T$. $\endgroup$ – Chris Peikert Jul 6 '19 at 14:50
  • $\begingroup$ The notations are confusing, but the question asks about the kernel lattice of $A^T$, so I don't see why that lattice should include the columns of $A^T$. $\endgroup$ – LeoDucas Jul 9 '19 at 15:12

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.