Can anyone tell me the difference between working in the polynomial embedding for $R$-LWE, and working in the canonical embedding?

  • $\begingroup$ Each one is just a linear transform, or change of basis, of the other: if a ring element is vector $v$ in the polynomial embedding, then it is $\Sigma v$ on the canonical embedding, for a certain matrix $\Sigma$. The key nice thing about the canonical embedding is that both addition and multiplication in the ring are coordinate-wise in the embedding. $\endgroup$ – Chris Peikert Jul 24 '20 at 2:13
  • $\begingroup$ By "polynomial embedding" do you mean representing a polynomial by its vector of coefficients? $\endgroup$ – Hilder Vitor Lima Pereira Jul 24 '20 at 7:56
  • $\begingroup$ Yes, specifically, the coefficient vector of the polynomial residue (remainder) modulo the polynomial defining the ring. $\endgroup$ – Chris Peikert Jul 26 '20 at 19:38

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.