2
$\begingroup$

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?


enter image description here


enter image description here


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

$\endgroup$
3
$\begingroup$

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

| improve this answer | |
$\endgroup$

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.