Score:0

# Why BFV relinearization works?

I was following why the BFV reliearization works, so I supposed 2 ciphertexts $$b_1$$ and $$b_2$$ and did the product:

$$b_1 = a_1s+e_1+\Delta m_1$$

$$b_1b_2 = (a_1s+e_1+\Delta m_1)(a_2s+e_2+\Delta m_2) = \\ a_1a_2s^2 + a_1se_2 + a_1s\Delta m_2 + e_1 a_2s +e_1e_2 + e_1\Delta m_2 + \\ \Delta m_1 a_2s + \Delta m_1 e_2 + \Delta ^2 m_1 m_2$$

We want to isolate $$\Delta m_1 m_2$$ in a way that we have $$as + e + \Delta m_1 m_2$$ so we can decrypt it.

$$\Delta^2 m_1m_2 + \Delta m_1a_2s + a_1s\Delta m_2+ e_0 + a_1a_2s^2 = \\\Delta ^2 m_1m_2 + \Delta s(m_1a_2 + a_1m_2) + e_0 + a_1a_2s^2$$

Let's imagine the relinearization key as

$$b_3 = a_3s + e_3 + s^2\implies a_1a_2b_3 = a_1a_2a_3s + a_1a_2e_3 + a_1a_2s^2$$

and we scaled it by $$a_1a_2$$ so we can subtract and remove the $$s^2$$ term from out $$b_1b_2$$ product:

$$b_1b_2- a_1a_2b_3 = \\ \Delta ^2 m_1m_2 + \Delta s(m_1a_2 + a_1m_2) + e_0 + \\a_1a_2s^2 - (a_1a_2a_3s + a_1a_2e_3 + a_1a_2s^2)$$

$$b_1b_2- a_1a_2b_3 = \Delta^2 m_1m_2 +\Delta s (m_1a_2 + a_1m_2) + e_0 -\\ a_1a_2a_3s + e_4$$

$$b_1b_2- a_1a_2b_3 = \\ \Delta^2 m_1m_2 +s (\Delta (m_1a_2 + a_1m_2 - a_1a_2a_3)) + e_5$$

The desire is to divide by $$\Delta$$ here but remember that $$(x \mbox{ mod q })/y \neq x/y \mbox{ mod q}$$ so we can't actually do:

$$round\left(\frac{b_1b_2- a_1a_2b_3 }{\Delta}\right) = \\ round(\Delta m_1m_2 +s (m_1a_2 + a_1m_2 - a_1a_2a_3) + e_6)$$

So how do I get the ciphertext to be in the form $$as + e + \Delta m_1m_2$$?

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