HEAAN

Given a plaintext vector ${\displaystyle {\vec {z}}=(z_{1},z_{2},...,z_{n/2})\in \mathbb {C} ^{n/2}}$ and a scaling factor ${\displaystyle \Delta >1}$, the plaintext vector is encoded as a polynomial ${\displaystyle m(X)\in R:=\mathbb {Z} [X]/(X^{n}+1)}$ by computing ${\displaystyle m(X)=\lfloor \Delta \cdot \phi ^{-1}({\vec {z}})\rceil \in R}$ where ${\displaystyle \lfloor \cdot \rceil }$ denotes the coefficient-wise rounding function.

Given a message polynomial ${\displaystyle m(X)\in R}$ and a scaling factor ${\displaystyle \Delta >1}$, the message polynomial is decoded to a complex vector ${\displaystyle {\vec {z}}\in \mathbb {C} ^{n/2}}$ by computing ${\displaystyle {\vec {z}}=\Delta ^{-1}\cdot \phi (m(X))\in \mathbb {C} ^{n/2}}$.

Here the scaling factor ${\displaystyle \Delta >1}$ enables us to control the encoding/decoding error which is occurred by the rounding process. Namely, one can obtain the approximate equation ${\displaystyle {\text{Dcd}}({\text{Ecd}}({\vec {z}};\Delta );\Delta )\approx {\vec {z}}}$ by controlling ${\displaystyle \Delta }$ where ${\displaystyle {\text{Ecd}}}$ and ${\displaystyle {\text{Dcd}}}$ denote the encoding and decoding algorithm, respectively.

From the ring-isomorphic property of the mapping ${\displaystyle \phi$ :\mathbb {R} [X]/(X^{n}+1)\rightarrow \mathbb {C} ^{n/2}} , for ${\displaystyle m_{1}={\text{Ecd}}({\vec {z}}_{1};\Delta )}$ and ${\displaystyle m_{2}={\text{Ecd}}({\vec {z}}_{2};\Delta )}$, the following hold:

• ${\displaystyle {\text{Dcd}}(m_{1}+m_{2};\Delta )\approx {\vec {z}}_{1}+{\vec {z}}_{2}}$,
• ${\displaystyle {\text{Dcd}}(m_{1}\cdot m_{2};\Delta )\approx {\vec {z}}_{1}\circ {\vec {z}}_{2}}$,

where ${\displaystyle \circ }$ denotes the Hadamard product of the same-length vectors. These properties guarantee the approximate correctness of the computations in the encoded state when the scaling factor ${\displaystyle \Delta }$ is chosen appropriately.

The key generation algorithm is following:

• Sample a secret polynomial ${\displaystyle s\leftarrow \chi _{s}}$.
• Sample ${\displaystyle a}$ (resp. ${\displaystyle a'}$) uniform randomly from ${\displaystyle R_{Q}}$ (resp. ${\displaystyle R_{PQ}}$), and ${\displaystyle e,e'\leftarrow \chi _{e}}$.
• Output a secret key ${\displaystyle sk\leftarrow (1,s)\in R_{Q}^{2}}$, a public key ${\displaystyle pk\leftarrow (b=-a\cdot s+e,a)\in R_{Q}^{2}}$, and an evaluation key ${\displaystyle evk\leftarrow (b'=-a'\cdot s+e'+P\cdot s^{2},a')\in R_{PQ}^{2}}$.

The encryption algorithm is following:

• Sample an ephemeral secret polynomial ${\displaystyle r\leftarrow \chi _{r}}$.
• For a given message polynomial ${\displaystyle m\in R}$, output a ciphertext ${\displaystyle ct\leftarrow (c_{0}=r\cdot b+e_{0}+m,c_{1}=r\cdot a+e_{1})\in R_{Q}^{2}}$.

The decryption algorithm is following:

• For a given ciphertext ${\displaystyle ct\in R_{q}^{2}}$, output a message ${\displaystyle m'\leftarrow \langle ct,sk\rangle }$ ${\displaystyle ({\text{mod }}q)}$.

The decryption outputs an approximate value of the original message, i.e., ${\displaystyle {\text{Dec}}(sk,{\text{Enc}}(pk,m))\approx m}$, and the approximation error is determined by the choice of distributions ${\displaystyle \chi _{s},\chi _{e},\chi _{r}}$. When considering homomorphic operations, the evaluation errors are also included in the approximation error. Basic homomorphic operations, addition and multiplication, are done as follows.

The homomorphic addition algorithm is following:

• Given two ciphertexts ${\displaystyle ct}$ and ${\displaystyle ct'}$ in ${\displaystyle R_{q}^{2}}$, output ${\displaystyle ct_{\text{add}}\leftarrow ct+ct'\in R_{q}^{2}}$.

The correctness holds as ${\displaystyle {\text{Dec}}(sk,ct_{\text{add}})\approx {\text{Dec}}(sk,ct)+{\text{Dec}}(sk,ct')}$.

The homomorphic multiplication algorithm is following:

• Given two ciphertext ${\displaystyle ct=(c_{0},c_{1})}$ and ${\displaystyle ct'=(c_{0}',c_{1}')}$ in ${\displaystyle R_{q}^{2}}$, compute ${\displaystyle (d_{0},d_{1},d_{2})=(c_{0}c_{0}',c_{0}c_{1}'+c_{1}c_{0}',c_{1}c_{1}')}$ ${\displaystyle ({\text{mod }}q)}$. Output ${\displaystyle ct_{\text{mult}}\leftarrow (d_{0},d_{1})+\lfloor P^{-1}\cdot d_{2}\cdot evk\rceil \in R_{q}^{2}}$.

The correctness holds as ${\displaystyle {\text{Dec}}(sk,ct_{\text{mult}})\approx {\text{Dec}}(sk,ct)\cdot {\text{Dec}}(sk,ct')}$.

Note that the approximation error (on the message) exponentially grows up on the number of homomorphic multiplications. To overcome this problem, most of HE schemes usually use a modulus-switching technique which was introduced by Brakerski, Gentry and Vaikuntanathan.[5] In case of HEAAN, the modulus-switching procedure is called rescaling. The Rescaling algorithm is very simple compared to Brakerski-Gentry-Vaikuntanathan's original algorithm. Applying the rescaling algorithm after a homomomorphic multiplication, the approximation error grows linearly, not exponentially.

The rescaling algorithm is following:

• Given a ciphertext ${\displaystyle ct\in R_{q}^{2}}$ and a new modulus ${\displaystyle q'<q}$, output a rescaled ciphertext ${\displaystyle ct_{\text{rs}}\leftarrow \lfloor (q'/q)\cdot ct\rceil \in R_{q'}^{2}}$.

The total procedure of the CKKS scheme is as following: Each plaintext vector ${\displaystyle {\vec {z}}}$ which consists of complex (or real) numbers is firstly encoded as a polynomial ${\displaystyle m(X)\in R}$ by the encoding method, and then encrypted as a ciphertext ${\displaystyle ct\in R_{q}^{2}}$. After several homomorphic operations, the resulting ciphertext is decrypted as a polynomial ${\displaystyle m'(X)\in R}$ and then decoded as a plaintext vector ${\displaystyle {\vec {z}}'}$ which is the final output.