Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
The content I ask in this question is in the following picture in [GPV08][1]. I do not understand the proof of the first claim in $\bf Lemma$ 5.2. In the proof, which reprensents the uniform distribution over $\mathbb{Z}_{q}^{n}$ and which represents $\bf{u=Ae} \mod q$.
Could someone explain it to me? Thanks!
[GPV08] Craig Gentry, Chris Peikert, Vinod Vaikuntanathan, [How to use a short basis: trapdoors for hard lattices and new cryptographic constructions][1], August 25, 2008.
The first claim has three steps to it:
Assumption of Primitivity: We want to make sure that the matrix $A$ isn't such that the function $x\mapsto Ax\bmod q$ (equivalently, $A$ viewed as a linear operator $\mathbb{Z}_q^m\to\mathbb{Z}_q^n$) "misses" most of its codomain. Imagine that $A$ is the all zero's matrix --- then the claim can't possibly be true!
If $q$ were prime we could assume that $A$ is "full rank" and this issue would disappear. We often don't like to restrict to the case that $q$ is prime though (for example, $q = 2^k$ is common in practice), so our matrices become defined over rings-that-aren't-fields, and "rank" can be a slightly problematic construct to work with (In particular, consider the lattice with basis matrix $\mathsf{diag}(2,1,1,\dots,1)$. If $q$ is not prime, this may not be equivalent to the identity matrix, so despite being "full rank" it will not surject).
Instead, we assume that $A$ is surjective as a map. This can be described several different ways in the literature (here it is "the columns generate the codomain", other places the term "is a primitive matrix" is used. When $A$ is a vector one can specify "the GCD of its entries is one"). This ends up being the right analogue of "$A$ is full rank" to use when working over rings-that-aren't-fields like $\mathbb{Z}/2^k\mathbb{Z}$. I believe this notion still works over number fields (so in the RLWE case) as everything can be viewed as an integer lattice still, but am less familiar with this area.
Near-uniformity of Discrete Gaussians mod the lattice: Lemma 2.8 states the following:
Let $\Lambda, \Lambda'$ be $n$-dimensional lattices with $\Lambda'\subseteq\Lambda$. Then, for any $\epsilon\in(0,1/2)$, any $s\geq \eta_\epsilon(\Lambda')$, and any $c\in\mathbb{R}^n$, the distribution of $(D_{\Lambda, s, c}\bmod \Lambda')$ is within statistical distance of at most $2\epsilon$ over $(\Lambda\bmod\Lambda')$
A useful simplification here is to set $\Lambda =\mathbb{Z}^n$. Then, this states that for any $n$-dimensional integer lattice $\Lambda'$, that for "large enough $s$" that $(D_{\mathbb{Z}^n, s, c}\bmod \Lambda')$ is within $2\epsilon$ being uniformly distributed over $\mathbb{Z}^n\bmod\Lambda'$, the fundamental domain of $\Lambda'$.
This is "what the smoothing parameter is defined for". The smoothing parameter specifies the "phase transition" between the Discrete Gaussian being non-uniformly distributed over the fundamental domain of $\Lambda'$ (when working mod the lattice of course), and it being very close to uniformly distributed (for a graphical demonstration of this, look at this other question). As long as we take $s$ larger than the smoothing parameter of the relevant lattice, the uniformity follows easily as a consequence.
The quotient group: It's worth mentioning explicitly what we should "expect $\mathbb{Z}^m/\Lambda^\perp$ to look like". Let $q$ be prime so everything is simpler. Recall that:
$$\Lambda_q^\perp(A) = \{x\in\mathbb{Z}^m \mid Ax \equiv 0 \bmod q\}$$
When $q$ is prime, this is just the kernel of the linear map $A : \mathbb{F}_q^m\to\mathbb{F}_q^n$. Then the group $\mathbb{Z}_q^m/\ker(A)\cong \mathsf{im}(A)$ by the first isomorphism theorem (for abelian groups). Of course we're dealing with $\mathbb{Z}^m/\ker(A)$ (no $\bmod q$ upstairs), but this doesn't actually matter --- as $\Lambda_q^\perp(A)$ is always $q$-ary (contains the sublattice $q\mathbb{Z}^m$), we have that all points in $\mathbb{Z}^m$ which differ by a point in $q\mathbb{Z}^m$ will be identified anyway, so we may as well pick representatives for these points and call them $\mathbb{Z}_q^m$, and "continue evaluating the quotient".
I'm under the impression this argument extends to the case of composite $q$ if one makes the appropriate substitutions of "linear algebraic arguments" to "module-theoretic arguments" along the way, but I haven't made the substitutions myself before, and don't feel like going through with it here. If someone has a reference I'd be interested.
Putting it together:
From here everything is fairly mechanical. We want to analyze the distribution of $(D_{\mathbb{Z}^m, s, c}\bmod\Lambda_q^\perp(A))$. By the second point this is within $2\epsilon$ (in statistical distance) of $\mathsf{Unif}(\mathbb{Z}^m/\Lambda_q^\perp(A))$. By the third point the underlying set of this is (assuming $q$ prime for simplicity) isomorphic to $\mathsf{im}(A)$, so the uniform distribution on the first set is identical to $\mathsf{Unif}(\mathsf{im}(A))$. Then, by the first point we have that $\mathsf{im}(A)\cong \mathbb{Z}_q^n$, so this distribution is simply $\mathsf{Unif}(\mathbb{Z}_q^n)$. In total, we end up with $(D_{\mathbb{Z}^m, s, c}\bmod\Lambda_q^\perp(A))$ being within $2\epsilon$ in statistical distance of $\mathsf{Unif}(\mathbb{Z}_q^n)$, which is the first claim.
