1
$\begingroup$

Given a matrix $\bf{A} \in \mathbb{Z}_q^{n \times m}$, then $$\Lambda_q^{\bot}(A) = \{y \in \mathbb{Z}^m: Ay = 0 \mod q\}$$ is a q-ary lattice. I am wondering whether $$\Lambda_q^{\bot}(A) = \{y \in \mathbb{Z}^m: Ay = b \mod q\}$$ for a given $b \neq \vec{0}$ is a lattice, too?

I would assume no, since it does not hold that: $A(y + y') = b$, for two $y, y'$ where $Ay = b$ and $Ay' = b$. If this is correct, is there any other way to construct a lattice that contains all solutions to the equation $Ay = b$?

$\endgroup$

1 Answer 1

1
$\begingroup$

If $b \neq 0 \ mod \ q$, you are right. Another way to argue is that a lattice must always contain $0$, but $A0 \neq b\ mod\ q$. From the definition of a lattice $\mathcal{L}$, if $y \in \mathcal{L}$ then $zy \in \mathcal{L}$ for any $z \in \mathbb{Z}$. So, if you want a lattice that contains all the solutions to the equation $Ay = b\ mod \ q$, then it will immediately contain all the solutions to the equation $Ay = zb\ mod \ q$ where $z \in \mathbb{Z}$. So, the simplest lattice I can come up with is $$\mathcal{L} = \{y \in \mathbb{Z}^m : Ay = zb\ mod \ q, z \in \{0,1, \dots, q-1\}\}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .