CKKS RNS encoding

Library Questions
1

Hello!

I having some trouble to understand how the encoding is in RNS representation and then how get encrypted.
I get that the encoding is in DCRT.
However when I want to get details of the theory, books like On Architecting Fully Homomorphic Encryption-based Computing Systems or papers like A Full RNS Variant of
Approximate Homomorphic Encryption, (if I understand correctly) it shows that they first encode the data and then in the encryption, they transforms it into an RNS representation.

For example in the paper appears that de encryption (page 11)

Enc_{pk}(m): For m ∈ R, sample v ← χ_{enc} and e_0, e_1 ← χ_{err}.
Output the ciphertext ct = (ct(j))_ {0≤j≤L} ∈ \prod^L_{j=0} R^2_{q_j} where ct^{(j)} ← v · pk^{(j)} + (m + e_0, e_1) (mod q_j ) for 0 ≤ j ≤ L.

And if I’m correct, that m is not in RNS…

How can I see/learn how it is done in OpenFHE?

2

It does not matter what representation is m in. That equation describes polynomial modular arithmetic which can be done in several ways. But to do it efficiently in CPU, RNS and DCRT representations are the currently best-known approaches to use.

I suggest you review a reference on RNS arithmetic for integers and polynomials. This is mandatory to understand RNS and DCRT arithmetic in OpenFHE. After you understand the theory, you can study the DCRT unittests in OpenFHE.

1 Like
3

I think I get it. However in my reasoning, I get that the RNS encryption are limb independent (something that I ask in other post), but when I test it in OpenFHE I get that are not independent. So I don’t know were I’m getting wrong.

Can you confirm my toy example?

Suppose that I have Q=105=q_0*q_1*q_2 =7*5*3, and m=47+23X=(47, 23)
So the RNS representation using <7,5,3> of each coefficient will be 47 = (5, 2, 2) and 23 = (2, 3, 2).
And this will be represented as 3 polynomials, m_0 = (5, 2), m_1 = (2, 3) and m_2 = (2, 2).

So when I want to encrypt this in a supper naive way (to only one polynomial and not two like CKKS), say adding to m the polynomial e=0+1X and the public key pk = 89 + 67X that in RNS is: pk_0=(5, 4), pk_1 = (4, 2) and pk_2=(2, 1)

So doing c_i = pk_i + m + e \text{ mod } q_i we have:
\begin{align} c_0&= pk_0 + m + e \text{ mod } q_0 = (5, 4) + (47, 23) + (0, 1) \text{ mod } 7 = (52, 28) \text{ mod } 7 = (3, 0)\\ c_1& =pk_1 + m + e \text{ mod } q_1 = (4, 2) + (47, 23) + (0, 1) \text{ mod } 5 = (51, 26) \text{ mod } 5 = (1, 1) \\ c_2& =pk_2 + m + e \text{ mod } q_2 = (2, 1) + (47, 23) + (0, 1) \text{ mod } 3 = (49, 25) \text{ mod } 3 = (1, 1) \end{align}

That is equivalent do this:
\begin{align} c_0&= pk_0 + m_0 + e \text{ mod } q_0 = (5, 4) + (5, 2) + (0, 1) \text{ mod } 7 = (10, 7) \text{ mod } 7 =(3, 0)\\ c_1& =pk_1 + m_1 + e \text{ mod } q_1 = (4, 2) + (2, 3) + (0, 1) \text{ mod } 5 = (6, 6) \text{ mod } 5 = (1, 1)\\ c_2& =pk_2 + m_2 + e \text{ mod } q_2 = (2, 1) + (2, 2) + (0, 1) \text{ mod } 3 = (4, 4) \text{ mod } 3 = (1, 1) \end{align}

That is the same. So in a sense, the calculation of each limb of the encryption c_i are only affected by the respective limb of the encoding m_i, right?

4

Yes, this is correct.

1 Like