Bootstrapping for Approximate Homomorphic Encryption

• 2020-11-03
• 2022-07-04

https://eprint.iacr.org/2018/153.pdf

Abstract

• LHEである CKKS scheme にbootstrapを実装してFHE化
• bootstrap: $2^6$ slots で 139s

Out Contribution

• 復号をHomEvalする
• Taylor展開は高次の多項式評価をする必要があるので, $\mathcal{O}(\sqrt{K_q})$ 深さが必要で厳しい
  • 2倍角の公式を $r$ 回使う

4.1 Packing Method

• 2べき $M>4$, $N=M/2$

• 5は mod $M$ で $N/2$ の位数 を持ち -1 で spans ${\mathbb{Z}}_M^{\ast }$ ??

  • ので, $\{{\zeta }_j,\overline{{\zeta }_j}:0\le j<N/2\}$ は原始 $M$ 乗根になる ${\zeta }_j:={\zeta }^{5^j}$

• $\tau :\mathbb{R}[X]/(X^{N+1)}\ni m(X)\mapsto z\in {\mathbb{C}}^{N/2}$ , $z_j=m({\zeta }_j)$

• (encode) $(N/2)\times N$ vandermonde行列で表せる
  

• 逆変換(decode)は $m=\frac{1}{N}({\bar{U}}^T\cdot z+U^T\cdot \bar{z})$

  • todo 確かめる

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}))$

5. Bootstrapping for HEAAN

5.1 Overview of the Recryption Procedure

MODRAISE -> COEFFTOSLOT -> EVALEXP -> IMGEXT -> SLOTTOCOEFF

Modulus raising

• $\mathrm{ct}=\mathrm{Enc}(m(X))(\mathrm{mod}q)$
• $t(X)=\mathrm{Enc}(t(X))(\mathrm{mod}{Q}_0)$
  • $t=qI+m$
• $m(X)=[⟨\mathrm{ct},\mathrm{sk}⟩{]}_q$

CoeffToSlot

• 同型評価するために $t$ の係数表現 $(t_0,\cdots t_{N-1})$ を slot に写したい → $\tau$ が使える
• $z^{\prime }=\tau (t)\in {\mathbb{C}}^{N/2}$ は $\mathrm{ct}$ に対応する平文だけどslot数が足りないので2つの暗号文にしまう
  • $z_0^{\prime }=(t_0,\cdots ,t_{N/2-1}),z_1^{\prime }=(t_{N/2},\cdots ,t_{N-1})$
  • $z_k^{\prime }=\frac{1}{N}({\overline{U_k}}^T\cdot z^{\prime }+U_k^T\cdot \overline{z^{\prime }})(k=0,1)$
  • これは線形変換を使って計算できる

HomEval

• Lattigo CKKS Bootstrap
• $F(t)=[t{]}_q$ の近似 $S(t)=\frac{q}{2\pi }\sin (\frac{2\pi it}{q})$ を評価

|F(t)-S(t)| = \frac{q}{2\pi}\left|\frac{2\pi m}{q} - \sin(\frac{2\pi m}{q})\right| \leq \frac{q}{2\pi} \cdot \frac{1} {3!} (\frac{2\pi |m|}{q})^{3} = \mathcal{O}(q \cdot \frac{|m|^3}{q^3})$$ - マクローリン展開で, $x - \frac{x^{3}}{3!} < \sin(x) < x$ より, $x - \sin(x) < \frac{x^3}{3!}$ - $E(t_{j})= E(qI_{j} + m_{j}) = \frac{q}{2\pi} \exp(\frac{2\pi im_{j}}{q})$ - $\pmod{q}$ だから?