In LPR12, page 4 is described a ring-LWE encryption in which we are working in a ring $R = \mathbb{Z}[x]/(x^n + 1)$ for a $n$ a power of 2. The public key is of the form $(a, b= a\cdot s + e)$ where $s$ is a secret key and $e$ a "small" element sampled form an error distribution. This is then generalized to other cyclotomic polynomials in LPR13.

I am trying to understand how to (efficiently) implement a sampler for e. As it is described, the distribution for $e$ is a discrete (or discretized) Gaussian but in a bit scaled and screwed space. Probably the easiest way to see it is as in CIV16, page 3 where they describe it by a linear transformation of a gauss sample. But implementing it in this way as a matrix multiplication seems inefficient. On the other hand, in papers like RVMCV14 it seems to me that there is no mentioning of any transformation.

I am asking what implementation would be preferred here? Actually I would be more than satisfied with an answer for when $R = \mathbb{Z}[x]/(x^n + 1)$ and $n$ is a power of 2.

  • $\begingroup$ When $n$ is a power of two, each coefficient of the polynomial error term is an independent (rounded/discrete) Gaussian. This is because the linear transform between the coefficient vector and the “canonical embedding” is a (scaled) orthogonal transform. $\endgroup$ – Chris Peikert Jun 30 '18 at 1:58
  • $\begingroup$ In the Newhope paper (usenix.org/conference/usenixsecurity16/technical-sessions/…) is described how discrete Gaussian can be replaced by a binomial distribution. $\endgroup$ – user27950 Jul 1 '18 at 15:43

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.