D-5.9 Decomposing Multiplication: DecompMult_RNS

In FHE, gadget decomposition (§A-6.4) is used to compute ciphertext-to-plaintext multiplication with small noise. For example, BFV and CKKS’s homomorphic key switching (Summary C-5 in §C-5) uses gadget decomposition to compute ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(\mathrm{\Delta }M)=B+A\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(S)$ with small noise (where each coefficient of the polynomial $A$ can be any value within the range of the ciphertext modulus $q$). As another example, the relinearization process of ciphertext-to-ciphertext multiplication in BFV (Summary D-2.7.5 in §D-2.7.5), CKKS (Summary D-3.5.6 in §D-3.5.6), and BGV (Summary D-4.8 in §D-4.8) uses gadget decomposition to derive the synthetic ciphertext ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(D_2\cdot S^2)$ when computing ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }({\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩})=D_0+D_1\cdot S+D_2\cdot S^2={\mathsf{\text{𝖼𝗍}}}_{\alpha }+{\mathsf{\text{𝖼𝗍}}}_{\beta }$, where ${\mathsf{\text{𝖼𝗍}}}_{\alpha }=(D_0,D_1)$, ${\mathsf{\text{𝖼𝗍}}}_{\beta }={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(D_2\cdot S^2)$, $D_0=B_1{B}_2$, $D_1=A_1{B}_2+A_2{B}_1$, and $D_2=A_1{A}_2$. Using gadget decomposition, we showed the following relations:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(A\cdot S)=⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(A),{\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S^{\prime },\sigma }^{\beta ,l}(S)⟩$ $▹$ used in key switching

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(D_2\cdot S^2)=⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(D_2),{\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(S^2)⟩$ $▹$ used in relinearization

However, if we convert a value (e.g., $x$) into an RNS vector, then it cannot be directly expressed in a gadget-decomposed form based on the $\beta$ and $l$ parameters. Instead, given the relationship between the value $x$ and its RNS residues is $x=\underset{i=1}{\overset{k}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}x\cdot {\displaystyle \frac{q}{q_i}}\cdot {\left|\left({{\displaystyle \frac{q}{q_i}}}^{-1}\right)\right|}_{q_i}modq$, we can treat each RNS residue as a gadget-decomposed element. For example, suppose our goal is to decompose ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(A\cdot S)$, where the RNS vector of $A=(A_1,A_2,\cdots ,A_k)$ has base moduli $(q_1,q_2,\cdots ,q_k)$. We can decompose ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(A\cdot S)$ as follows:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(A\cdot S)modq$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(S\cdot \left(A_1{\displaystyle \frac{q}{q_1}}\cdot {\left|{\left({\displaystyle \frac{q}{q_1}}\right)}^{-1}\right|}_{q_1}+A_2{\displaystyle \frac{q}{q_2}}\cdot {\left|{\left({\displaystyle \frac{q}{q_2}}\right)}^{-1}\right|}_{q_2}+\cdots +A_k{\displaystyle \frac{q}{q_k}}\cdot {\left|{\left({\displaystyle \frac{q}{q_k}}\right)}^{-1}\right|}_{q_k}\right)\right)modq$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(S\cdot A_1{\displaystyle \frac{q}{q_1}}\cdot {\left|{\left({\displaystyle \frac{q}{q_1}}\right)}^{-1}\right|}_{q_1}\right)+{\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(S\cdot A_2{\displaystyle \frac{q}{q_2}}\cdot {\left|{\left({\displaystyle \frac{q}{q_2}}\right)}^{-1}\right|}_{q_2}\right)+$

$\cdots +{\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(S\cdot A_k{\displaystyle \frac{q}{q_k}}\cdot {\left|{\left({\displaystyle \frac{q}{q_k}}\right)}^{-1}\right|}_{q_k}\right)modq$

$=A_1\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(S\cdot {\displaystyle \frac{q}{q_1}}\cdot {\left|{\left({\displaystyle \frac{q}{q_1}}\right)}^{-1}\right|}_{q_1}\right)+A_2\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(S\cdot {\displaystyle \frac{q}{q_2}}\cdot {\left|{\left({\displaystyle \frac{q}{q_2}}\right)}^{-1}\right|}_{q_2}\right)+$

$\cdots +A_k\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(S\cdot {\displaystyle \frac{q}{q_k}}\cdot {\left|{\left({\displaystyle \frac{q}{q_k}}\right)}^{-1}\right|}_{q_k}\right)modq$

$=\underset{i=1}{\overset{k}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\left(A_i\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(S\cdot {\displaystyle \frac{q}{q_i}}\cdot {\left|{\left({\displaystyle \frac{q}{q_i}}\right)}^{-1}\right|}_{q_i}\right)\right)modq$

, where ${\left\{{\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(S\cdot {\displaystyle \frac{q}{q_i}}\cdot {\left|{\left({\displaystyle \frac{q}{q_i}}\right)}^{-1}\right|}_{q_i}\right)\right\}}_{i=1}^k$ can be pre-generated as RNS key-switching keys.

Applying the same reasoning as above, we can also derive the following for relinearization:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(D_2\cdot S^2)=\underset{i=1}{\overset{k}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(D_{2,i}\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left(S^2\cdot {\displaystyle \frac{q}{q_i}}\cdot {\left|{\left({\displaystyle \frac{q}{q_i}}\right)}^{-1}\right|}_{q_i}\right))modq$

, where ${\left\{{\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left(S^2\cdot {\displaystyle \frac{q}{q_i}}\cdot {\left|{\left({\displaystyle \frac{q}{q_i}}\right)}^{-1}\right|}_{q_i}\right)\right\}}_{i=1}^k$ can be pre-generated as relinearization keys.

RNS-based multiplication decomposition is summarized as follows: