1
$\begingroup$

I am working on my master thesis which has as a main subject the CKKS algorithm. I am following the paper https://eprint.iacr.org/2016/421.pdf in which on page 8 it is mentioned that the encoding/decoding in the CKKS are isometric ring isomorphisms between $(S, \|\cdot \|_{\infty}^{can})$ and $(\mathbb{C}^{N/2}, \|\cdot \|_{\infty})$ where $S = \mathbb{R}[X]/(\Phi_M(X))$, $\Phi_M(X)$ a cyclotomic polynomial of degree $N = \phi(M), \|\cdot \|_{\infty}$ is the infinity norm and $\| m\|_{\infty}^{can} = \|\sigma (m)\|_{\infty}$ with $\sigma$ to be the canonical embedding between $S$ and $\mathbb{C}^N.$ I am trying to prove that the norms are preserved but all my attempts didn't work. What I am trying to prove is $\| Dec (m) \|_{\infty}=\|m\|_{\infty}^{can}$

Attempt 1 : $\begin{align*} \| Dec (m) \|_{\infty} = \| \pi \circ \sigma (\Delta^{-1}m)\|_{\infty} =\max\limits_i |\pi \circ \sigma (\Delta^{-1}m_i)| = \max\limits_i |\sigma (\Delta^{-1}m_i)|_{\infty} = \|\Delta^{-1}m\|_{\infty}^{can}= \Delta^{-1} \|m\|_{\infty}^{can} \end{align*} $
So I am ending up with a $\Delta^{-1}$ factor the I don't want

Attempt 2: On this one, I only focus on the form of the polynomials that I will use in the CKKS algorithm, or in other words, I assumed that my polynomial $m$ already carries a $\Delta$ factor, i.e, $m = \Delta m_1$ some polynomial $m_1$, but still:
\begin{align*} \|Dec(m)\|_{\infty} = \Delta^{-1} \|m\|_{\infty}^{can} = \Delta^{-1}\|\Delta m_1\|_{\infty}^{can} = \|m_1\|_{\infty}^{can} \end{align*}

getting a different polynomial from the one I started with, which doesn't seem to be what I need.

Can anyone help me out?

Thanks in advance

$\endgroup$

1 Answer 1

1
$\begingroup$

The statement "encoding and decoding are ismetric ... " appears to occur before any discussion of $\Delta$ occurs, so my reading is that they are discussing in the case of $\Delta = 1$ with that statement.

Separately, when they later discuss $\mathsf{Ecd}$ and $\mathsf{Dcd}$, they mention

$\mathsf{Dcd}(m; \Delta)$. For an input polynomial $m \in R$, output the vector $z = \pi \circ \sigma(\Delta^{-1} \cdot m)$, i.e., the entry of $z$ of index $j \in T$ is $z_j = \Delta^{-1} \cdot m(\zeta_M^j)$.

This is to say that (in the case $\Delta\neq 1$) they appear to additionally get this $\Delta^{-1}$ factor, similarly to how you do. This further suggests to me they only meant the spaces are isometric for $\Delta = 1$.

$\endgroup$

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.