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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.