I am currently trying to understand this Ring-LWE article: http://www.cims.nyu.edu/~regev/papers/ideal-lwe.pdf and I have a question.

Firstly, it is mentioned in the paper that we can view the elliptical Gaussian distributions $D_{\textbf{r}}$ (which are initially defined on $H$) as distributions on $K_{\mathbb{R}} =K \otimes_{\mathbb{Q}} \mathbb{R}$. Even though there isn't any explicit isomorphism mentioned there, I believe that $\varphi:K \otimes_{\mathbb{Q}} \mathbb{R} \to H$, $\varphi(x \otimes a) = a\sigma(x)$ makes sense in this context.

What I dont understand is the claim that the distribution $x \cdot D_{\textbf{r}}$ is equal to $D_{\textbf{t}}$, where $t_i =r_i \cdot |\sigma_i(x)| $, where $x \in K$. What I obtained is the following: if $x\in K$ and $y\in H$, $y=\sum_{i=1}^n y_i h_i$ (distributed $y \sim D_{\textbf{r}}$), then

(EDITED formula) $$xy= \sum_{i \in [s_1]} y_i \sigma_i(x)h_i + \sum_{i \in [s_2]}(y_{s_1+i}\cdot Re\sigma_{s_1+i}(x) - y_{s_1+s_2+i}\cdot Im \sigma_{s_1+1}(x)) h_{s_1+i}) +\sum_{i \in [s_2]}(y_{s_1+s_2+i} \cdot Re \sigma_{s_1+i}(x) + y_{s_1+i} \cdot Im \sigma_{s_1+i}(x))h_{s_1+s_2+i}$$ Basically I obtained the coefficients of $xy$ in base $\{h_1,h_2,\ldots,h_n\}$, and they dont seem to follow gaussian distributions with parameters $t_i = r_i \cdot |\sigma_i(x)|$ (except for the first $s_1$ of them)

Can anybody shed some light on this one ?


(I am one of the authors of the paper you're asking about. The isomorphism $\varphi$ you wrote is the intended one.)

The key observation is that a Gaussian $D_r$ of parameter $r$ over $\mathbb{C}$ is "spherical," i.e., it is the sum of independent Gaussians (both of parameter $r$) for the real and imaginary components, and so is invariant under rotations of the complex plane. Therefore, $x \cdot D_r$ equals $D_{|x| \cdot r}$ for any $x \in \mathbb{C}$.

The claim then follows by the fact that multiplication in $K$ corresponds to coordinate-wise multiplication in the real/complex components of $\sigma$. That is, the distribution of $x \cdot D_{(r_1,\ldots,r_n)}$ for $x \in K$ is just $D_{(|\sigma_1(x)| \cdot r_1, \ldots, |\sigma_n(x)| \cdot r_n)}$. (Note that the conjugate symmetry of the pairs of complex embeddings is preserved, as needed.)

  • 1
    $\begingroup$ Nice argument. I have a clearer picture now. I also edited the initial formula, which was incorrect, and the conclusion can be drawn also from there. Thanks $\endgroup$
    – Radu Titiu
    Jul 15 '15 at 12:28

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.