5
$\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 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)

Improve this question
$\endgroup$
4
  • $\begingroup$ @ChrisPeikert is occasionally seen here, he may be able to help you. $\endgroup$
    – puzzlepalace
    Sep 12, 2017 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, 2017 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, 2017 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, 2017 at 18:44

0

Reset to default

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.