In this paper I'm reading (specifically section 3.1), the authors say that the BFV encryption scheme supports plaintext multiplication, which basically means that given a ciphertext, $c$ that is an encryption of a plaintext $p_1$ and a plaintext, $p_2$, one can easily compute an encryption of $p_1 \cdot p_2$. What's more, this can be done without the evaluation key. How exactly does this "plaintext multiplication" work?
Any help is appreciated!
For the purposes of this paper, we recall that if $R:=\mathbb Z[X]/\langle X^n-1\rangle$, in BFV the plaintext space is $R_t:=R/tR$ and the ciphertext space $R_q^2$ where $R_q:=R/qR$ for some integers $t$ and $q$ with $q\gg t$. Encryption of the element $m(X)\in R_t$ is given by choosing low norm polynomials $u$, $e_0$ and $e_1$ and producing the ordered pair of polynomials $u(X)\mathrm{Enc}(0)+(e_0(X),e_1(X))+(\lfloor\frac qt\rfloor m(X),0)$. Note that rotating the coefficients of the polynomial pair corresponds to replacing $u(X)$ with $Xu(X)$, $e_i(X)$ with $Xe_i(X)$ and $m(X)$ with $Xm(X)$ as the first three are still polynomials of small norm, this corresponds to an encryption of $Xm(X)$.
It follows that just by rotating coefficients, we can write down encryptions $Xm(X), X^2m(X),\ldots, X^{n-1}m(X)$.
Now note that by using double-and-add methods we can compute $k\mathrm{Enc}(m(X))=\mathrm{Enc}(km(X))$ with at most $\log k$ additions. e.g. to compute $\mathrm{Enc}(13m(X))$ I compute $$\mathrm{Enc}(m(X))+\mathrm{Enc}(m(X))=\mathrm{Enc}(2m(X)),$$ $$\mathrm{Enc}(2m(X))+\mathrm{Enc}(m(X))=\mathrm{Enc}(3m(X)),$$ $$\mathrm{Enc}(3m(X))+\mathrm{Enc}(3m(X))=\mathrm{Enc}(6m(X)),$$ $$\mathrm{Enc}(6m(X))+\mathrm{Enc}(6m(X))=\mathrm{Enc}(12m(X)),$$ $$\mathrm{Enc}(12m(X))+\mathrm{Enc}(m(X))=\mathrm{Enc}(13m(X)).$$
Combining the above I can with at most $O(n\log t)$ additions compute $\mathrm{Enc}(f_0m(X)), \mathrm{Enc}(f_1Xm(X)),\ldots \mathrm{Enc}(f_{n-1}X^{n-1}m(X)),$ for any integers $f_i$ with $|f_i|<t/2$. With another $n-1$ homomorphic additions I can compute $$\mathrm{Enc}(f_0m(X))+\mathrm{Enc}(f_1Xm(X))+\cdots+\mathrm{Enc}(f_{n-1}X^{n-1}m(X))=\mathrm{Enc}(f(X)m(X))$$ where $f(X)=f_0+f_1X+\cdots+f_{n-1}X^{n-1}$. This is the encryption of my message multiplied by an arbitrary plaintext polynomial and was accomplished without any ciphertext multiplications nor knowledge of $\mathrm{Enc}(0)$.
In the notation of section 3.1 of the Angel et al paper, $c$ is $\mathrm{Enc}(m(X))$, $p_1(x)$ is $m(X)$ and $p_2(x)$ is $f(X)$.
