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$ – Chris Peikert Aug 10 '15 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$ – Miruna Rosca Aug 11 '15 at 12:51
  • $\begingroup$ Yes, that is correct -- see Definition 3.5. $\endgroup$ – Chris Peikert Aug 11 '15 at 14:36

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.