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.


1 Answer 1


Yes, this can be confusing at first. Maybe starting with a more recent paper could help: https://eprint.iacr.org/2018/117

In the paper I cited above they have improved the base conversion and scaling in RNS, but also made the procedures simpler as a side effect.

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

  • $\begingroup$ Please use $\LaTeX$ in your answers. For help, see this meta post. And, please check my modifications. $\endgroup$
    – kelalaka
    Commented Nov 11, 2018 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.