Score:1

encoding/decoding in the CKKS are isometric ring isomorphisms?

eg flag

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

Score:1
ng flag

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

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.