CKKS scheme

• Homomorphic Encryption for Arithmetic of Approximate Numbers で提案

Scheme

• $\mathrm{Setup}(1^{\lambda })$
  • ${\chi }_{key},{\chi }_{err},{\chi }_{enc}\leftarrow R$
  • 整数 $p$ を決め, レベル $L$ に対して modulus chain ${}^{\forall }\ell \in [1,L],q_{\ell }=p^{\ell }$
  • 整数 $P$ を選ぶ
• $\mathrm{Keygen}()$
  • sk
    • $s\leftarrow {\chi }_{key},\mathrm{sk}=(1,s)$
  • pk
    • $a\leftarrow U(R_{q_L}),e\leftarrow {\chi }_{err}$
    • $\mathrm{pk}=(b,a)\in R_{qL}^2$
    • Ring-LWE 性を満たす: $b+as=e$
  • evk
    • $a^{\prime }\leftarrow R_{P\cdot q_L}$, $e^{\prime }\leftarrow {\chi }_{err}$
    • $b^{\prime }=-a^{\prime }s+e^{\prime }+P{s}^2(\mathrm{mod}P\cdot q_L)$
• ${\mathrm{Enc}}_{pk}(m)$
  • $r\leftarrow {\chi }_{enc}$
  • $e_0,e_1\leftarrow {\chi }_{err}$
  • $\mathrm{ct}=r\times \mathrm{pk}+(m+e_0,e_1)(\mathrm{mod}{q}_L)$
    • $⟨\mathrm{ct},\mathrm{sk}⟩(\mathrm{mod}{q}_L)\approx m$
• ${\mathrm{Dec}}_{sk}(ct)$
  • レベル $\ell$ の暗号文で, $m=⟨\mathrm{ct},\mathrm{sk}⟩(\mathrm{mod}{q}_{\ell })$
  • $⟨({\mathrm{ct}}_0,{\mathrm{ct}}_1),(1,s)⟩={\mathrm{ct}}_0+{\mathrm{ct}}_1\cdot s$
• $\mathtt{Ecd}(z;\Delta )$
  • $N/2$ 次複素ベクトル $z=(z_i{)}_{i\in T}$ に対して, $m(X)={\sigma }^{-1}(\lfloor \Delta \cdot {\pi }^{-1}(z){\rceil }_{\sigma (R)})\in \mathcal{R}$
• $\mathrm{Dec}(m;\Delta )$
  • $z=\pi \circ \sigma ({\Delta }^{-1}\cdot m)$
• $\mathrm{Add}(\mathrm{ct},\mathrm{c}{\mathrm{t}}^{\prime })$
  • ${\mathrm{ct}}_{\mathrm{add}}=\mathrm{ct}+\mathrm{c}{\mathrm{t}}^{\prime }(\mathrm{mod}{q}_{\ell })$
• ${\mathrm{Mult}}_{\mathrm{evk}}(a,\mathrm{ct})$
  • $c_1=(b_1,a_1),c_2=(b_2,a_2)$
  • ${\mathrm{ct}}_{\mathrm{mult}}=(b_1{b}_2,a_1{b}_2+a_2{b}_1)+\lfloor P^{-1}\cdot a_1{a}_2\cdot \mathrm{evk}\rceil (\mathrm{mod}{q}_{\ell })$

$\{1,5,\cdots ,2\ell -3\}$ は ${\mathbb{Z}}_{2\ell }^{\times }$ の部分巡回群, $Y\mapsto Y^5$, $Y\mapsto Y^{-1}$ を評価することで回転や共役を計算できる $\mathrm{rk}$ や $\mathrm{ck}$ を公開する必要あり

• Bootstrapping for Approximate Homomorphic Encryption

• ${\mathrm{Mult}}_{\mathrm{evk}}(\mathrm{ct},\mathrm{c}{\mathrm{t}}^{\prime })$

• ${\mathrm{Rescale}}_{\ell \to {\ell }^{\prime }}(\mathrm{ct})$

• 精度を維持するためにscaling factorをかける

  • $\mathrm{Rescale}$ で調整

Encode/Decode

CKKS Encoding

演算

• Add: $a\oplus b$
  • ex. $[1,2,3,4]\oplus [5,6,7,8]=[6,8,10,12]$
• Mult: $a\odot b$
  • ex. $[1,2,3,4]\oplus [5,6,7,8]=[5,12,21,32]$
• Rotl: $a\ll k$
  • ex. $[1,2,3,4]\ll 2=[3,4,1,2]$
• GetIndex: $get\_index(a,i)\iff (a\odot {\mathrm{mask}}_{\{i\}})\ll i$
  • ex. $get\_index([1,2,3,4],1)=([1,2,3,4]\odot [0,1,0,0])\ll 1=[2,0,0,0]$
• SetIndex: $set\_index(a,i,v)\iff (a\odot {\mathrm{mask}}_{\{i{\}}^c})\oplus ({\mathrm{all}}_v\odot {\mathrm{mask}}_{\{i\}})$
  • ex. $set\_index(a,1,5)=([1,2,3,4]\odot [1,0,1,1])+([5,5,5,5]\odot [0,1,0,0])=[1,5,3,4]$

relinearize

• relinearize

Rotation

• シフト作用素 - Wikipedia
  • 有限数列のシフト作用素がもろシフト演算

4.2 Rotation and Conjunction

• KeySwitchingの目的: $s^{\prime }$ で暗号化された暗号文を別の秘密鍵 $\mathrm{sk}=(1,s)$ で同じ平分に復号されるような暗号文に変換すること
• 切り替え鍵 $\mathrm{swk}={\mathrm{KSGen}}_{sk}(s^{\prime })$ で作れる

${\mathrm{KS}}_{\mathrm{swk}}(\mathrm{ct})=(c_0,0)+\lfloor P^{-1}\cdot c_1\cdot \mathrm{swk}\rceil$

Rotation

• $\mathrm{ct}=\mathrm{Enc}(m(X))=\mathrm{Enc}(\mathrm{Ecd}(z))$ ($z=(z_j{)}_{0\le j<N/2}\in {\mathbb{C}}^{N/2}$)

• slot $i$ から $j$ に送る写像 ${\kappa }_k:m(X)\mapsto m(X^k)(\mathrm{mod}{\Phi }_M(X))$

  • $k:=5^{i-j}(\mathrm{mod}M)$ $M\perp k$
  • $\tilde{m}={\kappa }_k(m)$ は $\tilde{z}=(z_k{)}_{\forall j}$
  • $\widetilde{z_j}=\tilde{m}({\zeta }_j)=m({\zeta }_j^{5^{i-j}})=m({\zeta }_i)=z_i$
  • ${\kappa }_{5^r(\mathrm{ct})}=\mathrm{Enc}(\rho (z,r))$

• よって $\mathrm{Rot}(\mathrm{ct},r)={\mathrm{KS}}_{r{k}_r}({\kappa }_{5^r}(\mathrm{ct}))$

Link to original

RNS variant

• 係数の RNS 表現
  • A Full RNS Variant of Approximate Homomorphic Encryption

Bootstrapping

• Dec: $\mathrm{ct}\mapsto t=c_0+c_1\cdot s\mapsto [t{]}_q=\mu$

  • $t=qI+\mu$, some $||I||<K$

• modup: $\mathrm{Dec}(\mathrm{ct})=[c_0+c_1\cdot s{]}_Q=t$

• $t\mapsto [t{]}_q$ を 同型演算する

• naive: Taylor展開: 次数高いし不安定?

• Bootstrapping for Approximate Homomorphic Encryption

  • $\exp (i\theta /2^r)=\cos (\theta /2^r)+i\sin (\theta /2^r)$
    • 周期 $q$, 振幅 $\frac{q}{2\pi }$ にする todo なぜ?
    • 二倍角: $r$ 回2乗して $\exp (i\theta )$ が得られ, 虚部を取り出せば良い
  • ecd/dcdの線形変換は BSGS

• Improved Bootstrapping for Approximate Homomorphic Encryption

  • Chebyshev補間, 深さも最適化
  • ecd/dcdは $\tau$ の性質を用いた, FFT-styleアルゴリズム
  • Lattigo v2.0.0 で実装されている
    • Lattigo CKKS Bootstrap

• (2021) Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys

  • bootstrap x14
  • 多項式評価を最適化
  • Key-Switchを最適化 & 線形変換で double-hoisting を提案して最適化
  • Lattigo に実装した

参考文献

• The CKKS (a.k.a. HEAAN) FHE Scheme - YouTube
• https://simons.berkeley.edu/sites/default/files/docs/15661/2004simonsheaan.pdf
• 2022-04-19 01_encoding_decoding_ckks.ipynb - Colaboratory
• 2022-04-19 https://web.cs.ucla.edu/~nmanohar/nmanohar_files/PhDThesis.pdf
• 2022-04-19 Archive | 学而时习之
  • CKKS scheme, BFV scheme の解説
• 2022-04-20 Homomorphic Encryption intro: Part 2: HE landscape and CKKS | by Daniel Huynh | Towards Data Science
  • 紹介ブログ
• 2022-11-03 【秘密計算・準同型暗号】格子暗号（CKKS形式）を理解しよう - Qiita
• 2023-01-19 https://arxiv.org/pdf/2205.03511.pdf
  • 格子(SVP, CVP), Ring-LWE CKKS が載っているnoteがあった