Sample Extraction from RLWE to LWE

In this article I’ll derive a trick used in FHE called sample extraction. In brief, it allows one to partially convert a ciphertext in the Ring Learning With Errors (RLWE) scheme to the Learning With Errors (LWE) scheme. Here are some other articles I’ve written about other FHE building blocks, though they are not prerequisites for this article. Modulus Switching in LWE Key Switching in LWE The Gadget Decomposition in FHE Negacyclic Polynomial Multiplication Estimating the Security of Ring Learning With Errors LWE and RLWE The first two articles in the list above define the Learning With Errors problem (LWE).