Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$.

Let $s \gets R_q$ be a randomly selected secret. For $i=0,\dots,T-1$ we construct $p_i = sc_i + e_i$, where $c_i \gets R_q$ and $e_i \gets \chi$ are randomly selected.

Let $A_i = (c_i, p_i)$. Can we claim that the joint distribution of $A_0, ..., A_{T-1}$ is computationally indistinguishable from uniform? Can they jointly leak $s$?

  • 3
    $\begingroup$ This is exactly the (decisional) RLWE problem. And, the goal of recovering $s$ from the samples $A_i$ is exactly the search RLWE problem. $\endgroup$ – Chris Peikert Jun 5 at 21:31

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.