# Demystifying homomorphic multiplication in RNS FV variant

I am trying to understand a full RNS FV SWHE variant proposed in this paper.

My problem is with the homomorphic multiplication. Original ciphertexts are represented in RNS representation using base (say $q$ with $k$ co-prime moduli). In order to accommodate for coefficient growth, an auxiliary RNS base (say $\mathcal{B}_{sk}$ with $\ell$ co-prime moduli) is introduced. Note that $\{ q \cup \mathcal{B}_{sk} \}$ moduli are co-primes too and $k$ needs not to be equal to $\ell$. What I don't understand is the step (S3) in Algorithm 3 in page 13:

• The function "FastBconv" takes as input an extended ciphertext$^*$ in base $\{ q \cup \mathcal{B}_{sk} \}$. How to convert it to obtain a ciphertext in base $\mathcal{B}_{sk}$ only?
• There is also a strange notation of dots ($\dots$) used in the same line in the algorithm, what is that supposed to mean?

*: an extended ciphertext can be viewed as a matrix of $k+\ell$ rows and $n$ columns where $n$ is the underlying ring's polynomial modulus degree.

I appreciate any help in explaining the algorithm.

First, they expend the base of the ciphertext from $$Q$$ to $$Q*P$$, then they do the tensoring in $$QP$$, then they scale it down by $$t/Q$$ getting the result mod $$P$$, and then expend again the ciphertext (which is now in base $$P$$) to $$Q*P$$ and only keep the $$Q$$ part.
As for your question, if you have the ciphertext in base $$QP$$, and you want it only in base $$P$$, you can simply throw away the base $$Q$$ (delete the rows of the polynomial mod each $$q_{i}$$). Of course this is only valide If the value of the coefficients are within $$0,P-1$$. But this will always be the case since the auxiliary base $$P$$ is at least as big as $$Q$$. After multiplication this is not anymore the case because the coefficients will be of size $$Q^2$$ (unless $$P > Q^2$$). However after having them scaled down, they are back within the range of $$Q$$.
• Please use $\LaTeX$ in your answers. For help, see this meta post. And, please check my modifications. Commented Nov 11, 2018 at 17:36