# Random lattices

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.

## 1 Answer

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