I am currently trying to understand this Ring LWE article and I have a question. I don't understand how to apply Lemma 5.11 in order to get the worst case to average case reduction in Lemma 5.12, as long as Lemma 5.11 works for subsets of $\mathbb{R}^n$.

  • 1
    $\begingroup$ Can you clarify the difficulty you're having, and what your question is? Are you asking why Claim 5.11 deals with $\mathbb{R}^n$, while its application (in the proof of Lemma 5.12) deals with $R^\vee_q \times \mathbb{R}^n$? $\endgroup$ Aug 10, 2015 at 19:39
  • $\begingroup$ @ChrisPeikert Do you identify a distribution $\psi$ from $\Upsilon_\alpha$ with the vector $(x_1,\ldots,x_{n/2})$ where $x_i\sim\Gamma(2,1)$? If so, then Lemma 5.12 deals with $S\subset{R_q^{\vee}} \times \mathbf{R}^{n/2}$ and I see how Lemma 5.11 can be applied eventually. $\endgroup$ Aug 11, 2015 at 12:51
  • $\begingroup$ Yes, that is correct -- see Definition 3.5. $\endgroup$ Aug 11, 2015 at 14:36


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.

Browse other questions tagged or ask your own question.