Homomorphic Encryption intro Part 3 Encoding and decoding in CKKS

1. Preliminaries

$N=2^k,M=2Nm,{\Phi }_M(X)=X^N+1$

データ
$z\in {\mathbb{C}}^{\frac{N}{2}}$
を多項式の形
$m(X)\in \mathbb{Z}[X]/X^N+1$
へ変換する必要がある.

2. Vanilla encoding

$\sigma :\mathbb{C}[X]/(X^N+1)\to {\mathbb{C}}^N$ を見つける

decoding

${\Phi }_M(X)$ の $N$個の根 $\zeta ,{\zeta }^3,\cdots {\zeta }^{2N-1}$ を多項式に代入する
$\sigma (m)=(m(\zeta ),m({\zeta }^3),\cdots ,m({\zeta }^{2N-1}))\in {\mathbb{C}}^N$
($\sigma$ は全単射なので複素数と多項式が1対1対応)

encoding

$\sigma (m)=(m(\zeta ),m({\zeta }^3),\cdots ,m({\zeta }^{2N-1}))=(z_1,\cdots ,z_N)$
となるような
$m(X)={\sum }_{i=0}^{N-1}{\alpha }_i{X}^i$を見つける(${\alpha }_i$は係数)

つまり、
${\sum }_{j=0}^{N-1}{\alpha }_j({\zeta }^{2i-1}{)}^j=z_i\mathrm{for}\mathrm{i}=1,\cdots ,\mathrm{N}$

ヴァンデルモンド行列 $A$ を用いて
$A\alpha =z\iff \alpha =A^{-1}z$

Example

$M=8,N=4,{\Phi }_M(X)=X^4+1,\omega =e^{\frac{2i\pi }{8}}$ の時

根として $\zeta =\omega \simeq 0.707+0.707i$ を選ぶと

メッセージ $a=[1,2,3,4]$ は

$p:={\sigma }^{-1}(a)\simeq (2.5+4E^{-16}i)+(-5E^{-16}+0.7i)x+(-3E^{-16}+0.5)x^2+(-8E^{-16}+0.7i)x^3$

もう一度 $\sigma$ に通すと

$\sigma (p)\simeq [1-1E^{-16}i,2-4E^{-16}i,3+2^E-17i,4+2E^{-16}i]$

ほぼもとの値となっている

3. CKKS encoding

違うポイント

• 整数多項式環 $R=\mathbb{Z}[X]/(X^N+1)$ の多項式に変換
• decoder $\tau$ は要素が半分になるので共役を反転してくっつける