Improved Bootstrapping for Approximate Homomorphic Encryption

2022-07-04

CKKS Bootstrap

Youtube

2020-10-26

• https://www.youtube.com/watch?v=9cCnmgPZGfw

• HEAANのbootstrapはノイズへらない, regain level

• Dec: Dec_sk(c) = <c, sk> mod q

  • <c, sk> ~= m + q * I
  • c = enc(m + q * I mod Q >> q

• m + q * I |→ m

• Moduluar Reduction: Id ~= 0, q-周期

• 評価がscaledなsin関数: $\frac{q}{2\pi }\cdot (\frac{2\pi }{q}\cdot (m+q\cdot I))$

• Bootstrapの手順

  • 低いモジュラス q の暗号文 c = Enc(m(X)) [mod = q]
  • からより大きいモジュラス q_L に ModRaise
  • c = Enc(t(X)), q_L > q, t(X) = m(X) + q * I(X) [mod = q_L]

• 線型変換 CoeffToSlot で c は
  Enc(t_0, … t_(N/2)-1)
  Enc(t_(N/2), … t_N-1)
  FFTっぽくバタフライ演算(RotL と RotR で効率的にできる)
  DPでcollapsing pointsを見つけられる

• Sine Evaluation(scaled 指数評価, 虚部だけ抽出)
  Enc(m_0, … m_(N/2) - 1)
  Enc(m_(N/2) … m_N-1)
  評価 Taylor polynomial (d_0)
  Repeated Squaring (2^r)
  total degree d = d_0 * 2^r ~= 1000

• チェビシェフ補完
  sin (X) ~= \sum i = 0..d b_i * T_i (X)
  小さい d で精度がでる

• SlotToCoeff で q_L > q_l > q なものに
  c’ = Enc(m(X)) [mod = q_l]

• HEAAN-Boot+ 実装しました

• 課題

  • チェビシェフ補完をsigmoidとかRELUでやりたい
  • DFTをはやくしたい
  • HEAAN-RNSのbootstrapingを早くしたい

Abstract

• amortized time 0.01s (x100)
  • Level Collapsing: DFTみたいな線形変換
  • sin関数をTaylor近似からChebyshev近似にしてPatterson-Stockmayerアルゴリズムの修正版で評価

1. Introduction

1.1 Previous Bootstrapping Method for CKKS

• CKKS scheme from Homomorphic Encryption for Arithmetic of Approximate Numbers
• 毎回の乗算毎に 法 $q$ を減らしていく, iff メッセージのnormが $q$ よりも小さい時正しい
• そこで $q$ をより大きな法 $Q>q$ にしたい
  • todo 大きい法 $Q$ にmodswitchするのはなんで出来ないのか

Bootstrapping for Approximate Homomorphic Encryption では,

• 平文 $m(X)$ のとき小さな係数の多項式 $I(X)$ として $t(X)=m(X)+q\times I(X)$ に復号される.
• 係数に対して $\mathrm{mod}q$ を近似的に評価して $m_i=[t_i{]}_q$ を計算する
  • 指数関数 $\exp (2\pi it/(2^r\times q))$ のTaylor展開の $d$ 次の項を $2^r$ 乗して $\frac{q}{2\pi }$ かける

$$K_{d,r}(t)=\frac{q}{2\pi }{\left[\sum _{k=0}^d\frac{1}{k!}{\left(\frac{2\pi it}{2^{r}q}\right)}^k\right]}^{2^r}$$

虚部は $\frac{q}{2\pi }\times \sin \frac{2\pi t}{q}\approx [t{]}_q$

あとは, これを評価する前後で係数からスロットに変換とその逆をすれば良い
変換は Encode と Decode を準同型演算で表現すれば可能

Why the previous method does not scale well

• 近似精度を保証するために $d=\mathcal{O}(1),r=\mathcal{O}(\log q)$ で選ばれていた
• 指数関数の評価は $\mathcal{O}(\log q)$ ops, $\mathcal{O}(\log q)$ 深さ
• 線形変換は $\mathcal{O}(n)$ ops, $\mathcal{O}(1)$ 深さ
  • 暗号文がdenseだとスケールできない, レベルも改善できる

1.2 Our Contributions

• 線形変換をFFTぽくすることで 深さは必要だが, opsを少なく
  • レベルの消費量とopsのトレードオフを決定するのにDPを使った
  • 高速化かつslot数x2~x128に対応
• チェビシェフ補間で $\sin$ を近似することで精度高く, レベル減らせた ($\mathcal{O}(\log Kq)\to \mathcal{O}(\max (\log K+2,\log \log q))$) に($K$ は小さな定数)
  • ${\sum }^n{c}_k{T}_k(x)$ を効率的に評価するために パターソン・ストックマイヤーアルゴリズム を提案
    • mul ops $\mathcal{O}(\log (Kq))\to \mathcal{O}(\sqrt{\max ((4K,\log q))})$

2. Background

2.1 The CKKS Scheme

2べき $N$, $R:=\mathbb{Z}[X]/(X^N+1)$, 複素数ベクトル $\ell \le (N/2)$
$\zeta =\exp (\pi i/2\ell )$ を 2べき $\ell$ の $4\ell$ 番目の1の原始根

Decodeアルゴリズムは剰余多項式 $m(Y)\in \mathbb{R}[Y]/(Y^{2\ell }+1)$ をとって
$\mathrm{Decode}(m)=(m(\zeta ),m({\zeta }^5),\cdots ,m({\zeta }^{4\ell -3}))$ ($\mathrm{Decode}:\mathbb{R}[Y]/(Y^{2\ell }+1){\cong }^r{\mathbb{C}}^{\ell /2}$)

$m(Y)=(m_0,\cdots ,m_{2\ell -1})$ の係数表現とすると $\mathrm{Decode}$ は $\ell \times 2\ell$ 線形変換 $M_{\ell }\cdot m$

• $\mathrm{Encode}$ はその逆
  実装する時は$\ell \times \ell$ 特殊フーリエ変換行列 ${\mathrm{SF}}_{\ell }$ をつくって

$M_{\ell }=[\mathrm{S}{\mathrm{F}}_{\mathrm{\ell }}\mid i\times {\mathrm{SF}}_{\ell }]$

平文多項式($\mathbb{R}[Y]/Y^{2\ell +1}$)を $Y\mapsto X^{N/2\ell }$ で $\mathbb{R}[X]/(X^N+1)$ に埋め込む
暗号化された多項式は最も近い整数係数に丸め込む必要がある

• CKKS scheme
• Lattigo CKKS Bootstrap

2.2 Previous Bootstrapping for CKKS

• Bootstrapping for Approximate Homomorphic Encryption の手法を説明

• 暗号文のモジュラスを上げる(impl: Lattigo CKKS Bootstrap > Modup)

  • $[⟨\mathrm{ct},\mathrm{sk}⟩{]}_{Q_0}\approx q\times I(X)+m(Y)$
    • $I(X)$ の係数は ${\chi }_{key}$ に依存する定数 $K$ で抑えられる
    • subsum を実行する(impl: Lattigo CKKS Bootstrap > Subsum)
      • field extension $\mathbb{Q}[x]/(X^{N+1)}\ge \mathbb{Q}[Y]/(Y^{2\ell }+1)$
      • $\mathrm{c}{\mathrm{t}}^{\prime }\mathrm{where}⟨\mathrm{c}{\mathrm{t}}^{\prime },\mathrm{sk}⟩\approx (N/2\ell )\times t(Y)(\mathrm{mod}{Q}_0)$
      • $J(Y)=I_0+I_{N/2\ell }\times Y+\cdots I_{(2\ell -1)N/2\ell }\times Y^{N-1}$
      • $t(Y)=q\cdot J(Y)+m(Y)$

• 係数からベクトルへ($\mathrm{coeffToSlot}$) (impl: Lattigo CKKS Bootstrap > coeffsToSlots)

  • フーリエ変換の亜種を同型で評価することで実現出来る
  • some $Q_1$
  • 入力 $\ell$ 出力 $2\ell$ , $(t_0,\cdots t_{2\ell -1})$ なので2個並べる. $t_i=q\cdot J_i+m_i$

$|m|\ll q$ の時, $[t{]}_q=m\approx \frac{q}{2\pi }\sin (\frac{2\pi t}{q})$

$$P_{-r}(t)=\sum _{k=0}^d\frac{1}{k!}{\left(\frac{2\pi t}{2^r\cdot q}\right)}^k\approx \exp \frac{2\pi it}{2^r\cdot q}$$

3. Improved Linear Transforms from Level-Collapsing

• coeffToSlot, slotToCoeff の線形変換を改善する

3.1 FFT-like Algorithms

• slotToCoeff: $z\mapsto {\mathrm{SF}}_{\ell }\cdot z$
• coeffToCoeff: ${\mathrm{SF}}_{\ell }^{-1}$

Bootstrapping for Approximate Homomorphic Encryption では diagonal method と BSGS を採用

• DFTのバタフライ演算と同様に線形変換で出来る
  • 
  • ブートストラップの目的では bitReverse は不要
    • why: ビット反転は次数2の並べ換えだけど evalSine はSIMD演算なので並び替える必要ない
  • SIMD演算で表すと

$$w:=a[i]\odot w+b[i]\odot (w\ll 2^{i-1})+c[i]\odot (w\gg 2^{i-1})$$

• $a,b,c$ は事前に計算
  • todo どこから出てきたのか
• $\log \ell$ レベル, $\mathcal{O}(\ell )$ ops
• collapsing: 消費レベルとopsを交換できる

3.3 Optimal Level-Collapsing from Dynamical Programming

• Algorithms in HElib
  • claim 自分のやりたいことに近いので後で見る watchlater
  • タスク: 入力に 線形変換列 $L_1\circ \cdots L_{\ell }$ を適用する
    • 各線形変換はレベルを消費する, 変換をまとめることで最適化出来る
    • ex. $n=4$,$M_1=L_1\circ L_2,M_2=L_3\circ L_4$ と出来る
    • 最適なまとめ方を見つけるのはDPで
  • $w:=a[i+1]\odot \ast +b[i+1]\odot \ast \ll 2^i+c[i+1]\ast \gg 2^i$
  • $w:={\sum }_{i=1}^{k}p[i]\odot (w\ll t_i)$ みたいな形になる
  • $p[i],t_i$ 事前計算, $(k-1)$ rot と $k$ cmult で評価できる
    • BSGS も使えば $2\sqrt{k}$ rotまで削減
    • コストは cmult $\gg$ rot

4. Improved Sine Evaluation from Chebyshev Approximations

• Chebyshev Polynomials は多項式の集合 $\{T_n(x)\}$
  • $T_0(x)=1$
  • $T_1(x)=x$
  • $T_{2n}(x)=2T_n(x{)}^2-1$
  • $T_{2n+1}(x)=2T_n(x)\cdot T_{n+1}(x)-x$

リプシッツ連続関数 $f$ on $[-1,1]$ の $n$ 次 Chebyshev補間 は

$p_n^{\mathrm{cheb}}(x)={\sum }_{k=0}^n{c}_k{T}_k(x)$

• 詳細 todo
• Taylor展開による近似よりも低次数で優れた近似が出来る

4.3 Computing Cheebyshev Polynomials in FHE

• Chebyshev補間 の係数は事前に計算できる
  • スカラ乗算と加算を繰り返すと誤差小さく計算できるが $\mathcal{O}(n)$ 乗算が必要

Paterson-Stockmeyer for Chevbyshev

• todo BSGS と何が違うのか

• $\mathcal{O}(\sqrt{n})$ mult で済むが

  • $\{1,x,\cdots \}$ の基底で表せないと計算できないので書き換えないと無理(???)

watchlater