Random lattices

Question

The content I ask in this question is in the following picture in GPV08. I do not understand the sentence

computing the syndrome $\bf{Ae} \mod q$ for some $\bf{e} \in \mathbb{Z}^{m}$ is equivalent to reduce e modulo the lattice $\wedge^{\bot} (\bf{A})$.

Is it to say they are bijective or they are even equivalent in value (e+$\wedge^{\bot}$(A)=Ae mod q)? I think they are not equivalent in value. Is it right?

---

---

---

[GPV08] Craig Gentry, Chris Peikert, Vinod Vaikuntanathan, How to use a short basis: trapdoors for hard lattices and new cryptographic constructions, August 25, 2008.

Answer 1

The two expressions $e+\Lambda^\perp$ and $Ae\mod q$ can't really be equivalent in value since they are entirely different objects: One is a set of $m$-dimensional integer vectors, the other is a single $n$-dimensional vector.

What it means instead is that you can define a map from cosets of $\Lambda^\perp$ to syndromes of $A$ and it will be bijective. To define how this map operate, suppose we have a coset $e+\Lambda^\perp$. Pick any element $v$ of this set, and map the coset to $Av\mod q$.

We can see that this is well-defined by noting that every element in $e+\Lambda^\perp$ can be written as $e+v$ for some $v\in \Lambda^\perp$. The definition of $\Lambda^\perp$ says that $Av\equiv 0\mod q$ for all $v\in \Lambda^\perp$, so we have that $A(e+v)\equiv Ae\mod q$. Thus, the value of this map is the same no matter which representative of the coset we choose.

This is really just the first isomorphism theorem in disguise: $A$ is acting as a linear transformation of $\mathbb{Z}^m$; its image is the set of syndromes ($\mathbb{Z}_q^n$) and its kernel is $\Lambda^\perp$. So $\mathbb{Z}^m/\Lambda^\perp \cong \mathbb{Z}_q^n$.