1
$\begingroup$

In the paper GM18, they say that the sampling algorithm, SampleG, is shown in Figure 2. It takes as input a modulus $q$, an integer variance $s$, a coset $u$ of $\Lambda^{\perp}(g^T )$, and outputs a sample statistically close to $D_{\Lambda^{\perp}_u(g^T),s}$. SampleG relies on subroutines Perturb and SampleD where Perturb($\sigma$) returns a perturbation, $p$, statistically close to $D_{L(\Sigma_2),\sigma \cdot \sqrt{\Sigma_2}}$ , and SampleD($σ, c$) returns a sample $z$ such that $Dz$ is statistically close to $D_{L(D),−c,σ}$.

figure2

I can't really understand why SampleG outputs a sample statistically close to $D_{\Lambda^{\perp}_u(g^T),s}$, where the distribution is spherical(I think it's covariance should be $\sqrt{\Sigma_G}$, not $I$).

Also, I can't understand the meaning of $\beta$ in subroutin Perturb($\sigma$).

In addition, the perturbation $p$ statistically close to $D_{L(\Sigma_2),\sigma \cdot \sqrt{\Sigma_2}}$, why the lattice is $L(\Sigma_2)$, in other words, why the lattice basis is $\Sigma_2$.

I understand the framework of the SampleG algorithm in high level, but I am confused in pseudocode of the algorithm, anyone can help or discuss with me? Thanks a lot.

$\endgroup$

1 Answer 1

2
$\begingroup$

I am not an expert but here is my understanding. It is best to first understand [MP12]. A lot of this is to give background and not exactly on-point, also for my reference.

Question: Why does SampleG return a spherical distribution?

Answer: SampleG returns a spherical distribution because the authors are using the convolution technique, introduced in [Pei10], Theorem 3.1, and concretely used in MP12, Section 5.4, point (2). Let's look at MP12 first. The theorem statement is as follows, where $\Sigma_*$ are positive definite matrices and $\eta_{\varepsilon}(\Lambda) = O(\sqrt{\ln(n / \varepsilon)})$ is the smoothing parameter.

Theorem ([Pei10], Thm. 3.1): Let $\color{red}{\Sigma = \Sigma_1 + \Sigma_2}$ and lattices $\Lambda_1, \Lambda_2$ such that $\sqrt{\Sigma_1} \geq \eta_{\varepsilon}(\Lambda_1)$ and $\sqrt{\left(\Sigma_1^{-1} + \Sigma_2^{-1}\right)^{-1}} \geq \eta_{\varepsilon}(\Lambda_2)$. Consider the distribution of the output of the experiment

\begin{align*} \mathbf{x}_2 &\leftarrow \mathcal{D}_{\Lambda_2 + \mathbf{c}_2, \color{red}{\sqrt{\Sigma_2}}} \\ \mathbf{x}_1 &\leftarrow \mathbf{x}_2 + \mathcal{D}_{\Lambda_1 + \mathbf{c}_1 - \mathbf{x}_2, \color{red}{\sqrt{\Sigma_1}}} \\ &\mathrm{Output} \ \ \mathbf{x}_1 \end{align*}

Then, the (marginal) distribution of $\mathbf{x}_1$ is within statistical distance of $8\varepsilon$ of $\mathcal{D}_{\Lambda_1 + \mathbf{c}_1, \color{red}{\sqrt{\Sigma}}}$.

This theorem is significant in two ways, highlighted in $\color{red}{\text{red}}$. For one, it guarantees the distributions of summing two Gaussian variables. Looking the other direction, it also means you can split sampling from one distribution into sampling from two other distributions, if they are more convenient.

It is exactly what's done in MP12 and GM18: They are trying to sample preimages from $\mathcal{D}_{\Lambda^{\perp}_{\mathbf{u}}(\mathbf{G}), s}$ with covariance $\Sigma = s\mathbf{I}_n$, for which there is a straightforward way that outputs vectors with covariance $\Sigma_1 = \begin{bmatrix} \mathbf{R} \\ \mathbf{I} \end{bmatrix} \Sigma_{\mathbf{G}} \begin{bmatrix} \mathbf{R}^T & \mathbf{I} \end{bmatrix}$, so if we use the convolution theorem above, we can simply sample a perturbation $\mathbf{p}$ from a distribution with $\Sigma_2 = \Sigma - \Sigma_1$, then sample from the preimage of $\mathbf{u - Ap}$ instead of $\mathbf{u}$. More concretely, they sample directly from $\mathcal{D}_{\mathcal{L}(\Sigma_2), s\sqrt{\Sigma_2}}$, which there is an extremely simple sampler (Klein's, see [[MP18]], Figure 1) because the "bases are aligned"!

To show it even more clearly, here is an alternative presentation of SampleG:

\begin{align*} \sigma &:= s / r \\ \mathbf{p} &\leftarrow \operatorname{Perturb}(\sigma) \\ \mathbf{c} &:= \mathbf{B}_{b^k}^{-1}(\mathbf{u} - \mathbf{p}) \\ \mathbf{z} &\leftarrow \operatorname{SampleD}(\sigma, \mathbf{c}) \\ \mathbf{t} &:= \mathbf{B}_q\mathbf{z} + \mathbf{u} \\ &\text{Output} \ \mathbf{t} \end{align*}

Where Perturb and SampleD are algorithms such that $\mathbf{p} \sim \mathcal{D}_{\mathcal{L}(\Sigma_2), \sigma\sqrt{\Sigma_2}}$ and $D\mathbf{z} \sim \mathcal{D}_{\mathcal{L}(D), -\mathbf{c}, \sigma}$. To simplify it even more, note that

$$ \mathbf{B}_q\mathbf{z} + \mathbf{u} = \mathbf{B}_{b^k}(D\mathbf{z} + \mathbf{B}_{b^k}^{-1}\mathbf{u}) = \mathbf{B}_{b^k}(D\mathbf{z} + \mathbf{c}) + \mathbf{p} $$

so the algorithm can be written as

\begin{align*} \sigma &:= s / r \\ \mathbf{p} &\leftarrow \mathcal{D}_{\mathcal{L}(\Sigma_2), \sigma\sqrt{\Sigma_2}} \\ \mathbf{z}' &\leftarrow \mathcal{D}_{\mathcal{L}(\mathbf{B}_q) + \mathbf{u} - \mathbf{p}, \color{blue}{\sigma\mathbf{B}_{b^k}}} \\ \mathbf{t} &:= \mathbf{p} + \mathbf{z}' \\ &\text{Output} \ \mathbf{t} \end{align*}

where, of course, $\color{blue}{\sigma\mathbf{B}_{b^k}} = \sigma\sqrt{\Sigma_1}$


Question: What is the significance of $\beta$ in Perturb?

Answer: It is an "unrolled" version of the randomised nearest plane algorithm, described in [GPV08] section 4.2, combined with the compact upper triangular representation of $\sqrt{\Sigma_2}$ in ([GM18]) section 3.1. You can derive it yourself by unwrapping the dot products in the [GPV08] description. This is exactly why having a simple (sparse) $\sqrt{\Sigma}$ is important - it allows for efficient sampling!


Question: Why is the lattice $\mathcal{L}(\Sigma_2)$ in Perturb?

Answer: I think I answered above. It can be chosen arbitrarily, since you can just adjust the other matrix in the convolution theorem above. Also, sampling for $\mathcal{D}_{\mathcal{L}(\Sigma), \sqrt{\Sigma}}$ is extremely quick.


I highly recommend first understanding [MP12]'s framework especially with perturbation sampling (section 5.2). The difference between [MP12] and [GM18] essentially lies in finding an efficient factorisation of $\sqrt{\Sigma_2}$, but the sampling is essentially the same.

Best,

$\endgroup$
2
  • 1
    $\begingroup$ It is also perhaps worth noting that the various convolution theorems for discrete gaussians have been superseded by this, which might be a good resource to look into for details about how discrete gaussians may be combined. $\endgroup$
    – Mark
    Sep 25 at 19:48
  • $\begingroup$ @Mark Thanks, I was not aware of that, it seems quite useful :) $\endgroup$
    – Gareth Ma
    Sep 26 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.