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

Improve this question
$\endgroup$
1
  • 2
    $\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, 2019 at 14:48

1 Answer 1

Reset to default
4
+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$
2
  • $\begingroup$ The basis would not be $qI$ because that does not include the columns of $A^T$. $\endgroup$
    – Chris Peikert
    Jul 6, 2019 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, 2019 at 15:12

Your Answer

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

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