Score:1

Plaintext Multiplication in BFV

at flag

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!

Score:1
ru flag

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)$.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.