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$ Jul 24, 2020 at 2:13
  • $\begingroup$ By "polynomial embedding" do you mean representing a polynomial by its vector of coefficients? $\endgroup$ Jul 24, 2020 at 7:56
  • $\begingroup$ Yes, specifically, the coefficient vector of the polynomial residue (remainder) modulo the polynomial defining the ring. $\endgroup$ Jul 26, 2020 at 19:38


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.