ring-LWE: Minkowski Embedding , the Co-Different Ideal, etc

While (trying) to go over the reductions from approx. SVP on ideal lattices to search ring-LWE, [1] and [2], for $$K = \mathbb{Q}(\zeta)$$ where $$\zeta$$ is an abstract root of a cyclotomic polynomial, the ring-LWE error distribution $$\psi$$ is defined over $$K_\mathbb{R} = K \otimes_{\mathbb{Q}} \mathbb{R} \cong \mathbb{R}^{s_1} \times \mathbb{C}^{2s_2}$$ where $$n = s_1 + 2s_2$$ is the degree of $$K$$ and $$\mathbb{R}^{s_1} \times \mathbb{C}^{2s_2}$$ is a space that embeds $$K$$ under the Minkowski or "canonical" embedding [1].

Question 1: I take this to mean that the error is sampled directly as a vector from a Gaussian (discretized) over the space $$\mathbb{R}^{s_1} \times \mathbb{C}^{2s_2} \cong \mathbb{C}^n$$, i.e. for the error, does the reduction require sampling directly from the canonical embedding rather than the "co-efficient embedding" in the polynomial basis of $$K$$ (i.e. a power basis) followed by somehow "pulling back" from $$\mathbb{R}^{s_1} \times \mathbb{C}^{2s_2}$$ to the polynomial basis (I pose the question for general cyclotomics rather than just "power of 2" cyclotomics). Or does the reduction work by starting with error samples in the co-efficient embedding and then subjecting these to the canonical embedding?

Question 2: Regardless of how the reduction works, I am guessing that in practice, for general cyclotomics (i.e. not simply for the power of 2 cyclotomics), it is sufficient to simply sample from the co-efficient embedding of $$K$$, so that for a centered spherical error, for eg., it is ok to independently sample each integer coefficient of the error polynomial from a discretized 1-D Gaussian of appropriate width (if one is willing to forego efficiencies for polynomial multiplication in the canonical embedding)?

Question 3: For the power of 2 cyclotomics, given the isometry of the two embeddings, is it safe in practice to sample directly from the co-efficient embedding of $$K$$ as described in Q2 above?

[1] Also employs the fact that fractional ideals of $$K$$ canonically embed as lattices. The ring-LWE secret is drawn from a distribution over the fractional ideal $$R^V$$ where $$R = \mathcal{O}_K$$. So $$R^V$$ is presented as the dual of $$R$$ under a trace product (and itself embeds as a lattice which is also presumably the dual lattice of the embedding of $$R$$) and referred to as the "co-different" ideal.

Question 4: What is the rationale for drawing the secret from $$R^V$$ as opposed to the error distribution. $$\psi$$ over $$K_\mathbb{R}$$. Does this aid in implementation, or is this choice central to the proof?

Question 5: Why is the full ring-LWE instance then reduced mod $$qR^V$$ for some integer $$q = 1 \ mod \ 2n$$ rather than just taken to be an element in $$K_\mathbb{R}/qK_\mathbb{R}$$ (see Def. 3.1 in [1])?

Question 6: As a result, the second component of a ring-LWE instance is then taken to be an element in $$K_\mathbb{R}/qR^V$$ (def. 3.1 in [1]). [2] on the other hand talks of $$R^V$$ as a "decoding basis". What is the relationship between an element in the "decoding basis" and a ring-LWE instance of the form $$R_q \times K_\mathbb{R}/qR^V$$ from def 3.1 in [1]? I am guessing that an element from $$K_\mathbb{R}/qR^V$$ may be multiplied by some scaling factor to obtain the corresponding element in $$R^V_q$$. What is the typical basis for $$R^V$$? Is it simply a scaled version of the co-efficient basis of $$R$$?

Question 7: [3] On the other hand eschews (1) the error distribution. over $$K_\mathbb{R}$$ and (2) the secret distribution. over $$R^V$$ and seems to sample both from $$R_q$$ thus making the ring-LWE instance a tuple in $$R_q \times R_q$$. Is this purely owing to the choice of power of 2 cyclotomic in this work?

Question 8: About 37 mins into the recording [4] Lyubashevsky talks about the Chinese Remainder representation of and element in $$R$$. What is the relationship between this and the canonical embedding, is it the same thing?

[1] Lyubashevsky, Vadim and Peikert, Chris and Regev, Oded, "On Ideal Lattices and Learning with Errors over Rings". J. ACM, November 2013 Vol.60/6, 2013.

[2]Vadim Lyubashevsky and Chris Peikert and Oded Regev, "A Toolkit for Ring-LWE Cryptography". Cryptology ePrint Archive, Report 2013/293}, 2013.

[3]Chris Peikert "Lattice Cryptography for the Internet", Cryptology ePrint Archive Report 2014/070, 2014

[4] Vadim Lyubashevsky, Lecture at 2nd Bar Ilan University Winter School on Cryptography: Ideal Lattices and Applications (https://www.youtube.com/watch?v=Eg_pyyeT_Qc&feature=plcp)

• @ChrisPeikert is occasionally seen here, he may be able to help you. Sep 12, 2017 at 21:42
• I am not an expert in that field and therefore cannot give you a definite answer but maybe that hint helps. As far as I understand, one always samples form $K_\mathbb{R}$ . $K_\mathbb{R}$ is basically the space of the polynomial coefficients embedded in $\mathbb{R}$. $K_\mathbb{R}$ is not $H$ , it is only isomorphic to $H$.
– user27950
Sep 14, 2017 at 20:48
• @Cryptostasis that is informative, yes I see that $K_\mathbb{R}$ is only \iso to $H$ so seems like what you're saying is that reductions require sampling from $K_\mathbb{R}$. From what I can see most applications (eg. Peikert's KEM and the BGV cryptosystem) over 2 power cyclos sample both the secret and the error from distributions over $R_q$ - I think this is a variant of RLWE called polynomial LWE or PLWE Hermite Normal Form that is the form I have commonly seen in applications. Sep 14, 2017 at 22:44
• For general cyclotomics, isn't it the case that norms in $K_\mathbb{R}$ would be different from norms in $H$ (especially for products), it's not clear how the reduction bounds could be obtained by considering polynomials in $K_\mathbb{R}$, esp. given the following statement in [1] that seems to be important for the proofs - " ..under the canonical embedding both addition and multiplication of ring elements are simply coordinate-wise. As a result, both operations have simple geometric interpretations that lead to tight bounds, and product distributions (such as Gaussians) behave very nicely .." Sep 15, 2017 at 18:44