I know this question fits more in the crypto portal, but I could not get any answer/comment since I posted it there 3 days ago. I am trying to understand this paper which shows a Residual Number System (RNS) variant of the FV Somewhat Homomorphic Encryption (SWHE) scheme. I managed to understand the decryption procedure but I am fining some troubles in multiplication.
The basic idea of the paper can be summarized as follows: in the original FV scheme, we need to perform exact division and rounding procedures. This incurs us to move to positional representation system since we usually perform computation in RNS system. However, the author claim they can do that without conversion.
I will show here a very simple example following the paper's directions and would appreciate if someone can find where are the problems:
Let,
$\mathcal{P}=\{3,5\}$ original RNS basis,
$\mathcal{B}={7}$ extended RNS basis,
$m_{sk}=13$ a redundant modulus,
$t=1$, $q=15$ $\in \mathbb{Z}$.
Let, $c_1=14$, $c_2=1$ both $\in\mathbb{Z_q[X]/\langle X^{2^n}+1 \rangle}$ be two ciphertexts (for simplicity I choose constant polynomials and the exact value of $n$ is irrelevant here I guess ).
Objective is to calculate: $c_3 = \lceil \frac{t}{q}*(c_1*c_2)\rfloor$.
It is easy to calculate $c_3=\lceil \frac{1}{15}*(1*14)\rfloor=1$ in positional number system.
According to the paper, to calculate $c_3$ in RNS system, the following steps to be followed:
Step 1: extend the input ciphertexts into an auxiliary RNS basis $\mathcal{Bsk} = Join[\mathcal{B},m_{sk}]$ that can accommodate the largest value of their product.
Hence, $c_1=\langle 2, 4 \rangle$ in base $\mathcal{P}$ is extended to $\langle 2, 4, 0,1 \rangle$ in base $\mathcal{Bsk}$. Similarly, $c_2=\langle 1, 1, 1, 1 \rangle$.
Step 2: mutliply $c_1*c_2= c_3' =\langle 2, 4, 0, 1 \rangle$.
Step 3: use the procedure $fastRNSFloor_q(t*c_3',\mathcal{Bsk})$ to obtain $\lceil \frac{t}{q}*(c_3')\rfloor + b$, where $|b|<(|\mathcal{P}| = 2)$.
The result from this step is $\langle 5, 11 \rangle$ in base $\mathcal{Bsk}$ which is equal to 89 in decimal. The product $c_3$ in $\mathcal{Bsk}$ is just 1 in decimal. The difference $89 -1 = 88$ is much larger than $2$.
Appreciate any help in this problem.
Note that there is another step to go back to base $\mathcal{P}$.