3
$\begingroup$

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 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 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 distrib. $\psi$ over $K_\mathbb{R}$. Does this aid in implementation, or is this choice central to the proof?

Question 5: Why is the 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 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 distrib. over $K_\mathbb{R}$ and (2) the secret distrib. 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)

$\endgroup$
  • $\begingroup$ @ChrisPeikert is occasionally seen here, he may be able to help you. $\endgroup$ – puzzlepalace Sep 12 '17 at 21:42
  • $\begingroup$ 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$. $\endgroup$ – user27950 Sep 14 '17 at 20:48
  • $\begingroup$ @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. $\endgroup$ – Rohit Khera Sep 14 '17 at 22:44
  • $\begingroup$ 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 .." $\endgroup$ – Rohit Khera Sep 15 '17 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.