Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys

CKKS Bootstrapping, CKKS-RNS, MultMatVecの話とか全部入りでかなりわかりやすそう

Abstract

• 以前のBootStrappingより高速化
• 近似的なReScalingを考慮したレベル消費量が最適な同型多項式評価のための汎用アルゴリズムを提案
  • “double hoisting”: キースイッチの手順を最適化して線形変換のための新たな手法
• BootStrappingをパラメータ化するための体系的なアプローチ
• lattigoに実装された
  ${\mathbb{C}}^{32768}$ のbootstrapに18s (x14.1)

1. Introduction

今までのBootstrappingは回路深さを削減するために sparse secret-keysを使ってた.
これは128bit securityを担保できていない.
ので規格化の際にBootstrapを除外している -> 実用性アレ

Homomorphic Polynomial Evaluation

Section3で紹介, RNS-variantではRescalingがモジュラス$Q$ の係数
$q_i$ での除算のみに制限されているので2の累乗で行えずスケールのずれが生じる
多項式評価のような複雑な回路では誤差につながる
定数の平文を 次のrescaleの $q_i$ でrescaleすることで線形回路では自明に解決できる
-> 暗号文のスケールは演算後も変化しない
多項式は1次式の評価の組み合わせなので汎用化
$\lceil \log (d+1)\rceil$
レベル消費して $d$ 次多項式を評価できる
指定されたscaleからはじめ, 再帰的にscaleを伝播させ同じscaleですべての演算が行えることが保証される(=誤差が出ない)

Faster Matrix x Ciphertext Products

Section4, 演算で最もコストがかかるのはキースイッチだけど乗算, 回転演算, 共役で必須.
Bootstrappingでも大量の回転を伴う2つの線形変換が必要なのでキースイッチの数を最小限に抑えることは性能向上に貢献
$n\times n$ の平文行列 $M$ と暗号化されたベクトル $v$ との積の計算には BSGS を使用して $\mathcal{O}(\sqrt{n})$ 回転で $Mv$ を計算
これらはKey-switchをブラックボックスで扱い実行回数を削減するので
hoisting を利用していない.
我々は回転鍵の新しいフォーマットと hoisting
をsecond-layerまで拡張する修正されたkey-switchingを提案することで BSGS を改善.
これは一般的に使えて, 暗号文の線形変換の複雑度(modular productの観点から(?))を削減
線形変換のコストを50%に

Improved Bootstrapping Procedure

Section 5

Parameterization and Evaluation

Section 6, CKKS schemeのパラメータ化とBooststrap回路について説明し, ユースケースに併せてパラメータを選択, 調整する手順を提案,
lattigo
に実装したよ
CKKS-RNSでのbootstrappingの最初のオープンソースの実装.
HEAAN.jl にもRNS-variantでBootstrap実装されていたような

2. Background and Related Work

2.1 The Full-RNS CKKS scheme

CKKS scheme の full-RNS variant というのは多項式の係数が
RNS表現
されていること.

Notation

2べき $N$
$L+1$ の異なる素数
$q_0,\cdots ,q_L$, $Q_L:={\prod }_{i=0}^L{q}_i$

$$R_{Q_L}:={\mathbb{Z}}_{Q_L}[X]/(X^N+1)$$

は 有限体

$Q_L$ 係数のcyclotomic多項式環
一意にRNS

$$R_{q_0}\times \cdots \times R_{R_{q_L}}\cong R_{Q_L}$$

が定まり, 元は
$(L+1)\times N$
の係数の行列となる.
スカラはitallicで書き, ベクトルはboldで書く.
$a^{(i)}$: ベクトルの $i$ 要素目, 多項式の $i$ 次目
$\Vert a\Vert$ : 無限ノルム
$\mathrm{hw}(a)$ : ハミング重み
$⟨a,b⟩$ : 内積

$$ϵ:=\frac{1}{n}\sum _{i=0}^{n-1}|a^{(i)}-b^{(i)}|$$

$[x{]}_Q$ : x % Q

Plaintext and Ciphertext Space

平文は多項式

$\mathrm{pt}=m(Y)\in \mathbb{R}[Y]/(Y^{2n}+1)$, $Y:=X^{N/2n}$ , $n<N$ , $n$ 2べき
平文: $\{\mathrm{pt},Q_{\ell },\Delta \}$, $\mathrm{pt}\in {\mathrm{R}}_{{\mathrm{Q}}_{\mathrm{\ell }}}$
暗号文: $\{\mathrm{ct},Q_{\ell },\Delta \}$, $\mathrm{ct}\in {\mathrm{R}}_{{\mathrm{Q}}_{\mathrm{\ell }}}^2$
$\Delta$ : スケール係数

$Q_{\ell }:={\prod }_{i=0}^{\ell }{q}_i$ : レベル
$\ell$ のモジュラス($0\le \ell \le L$ )

Scheme RNS-CKKS

(省略)

$\mathbf{SwitchKeyGen}(s,s^{\prime },\mathbf{w})$
$\mathbf{w}$ は $\beta$ 要素持つ
sample $a_i\in R_{P{Q}_L}$ , $e_i\leftarrow {\chi }_{\mathrm{err}}$
returns key-switch key

${\mathrm{swk}}_{s\to s^{\prime }}:=({\mathrm{swk}}_{s\to s^{\prime }}^{(0)},\cdots )$
, where ${\mathrm{swk}}_{s\to s^{\prime }}^{(0)}=(-a_i{s}^{\prime }+s{w}^{(i)}P+e_i,a_i)$

$\mathbf{PubKeyGen}(s)$

public encryption key

$$\mathrm{pk}\leftarrow \mathbf{SwitchKeyGen}(0,s,(1))$$

relinearization key

$$\mathrm{rlk}\leftarrow \mathbf{SwitchKeyGen}(s^2,s,w)$$

rotation keys

$${\mathrm{rot}}_k\leftarrow \mathbf{SwitchKeyGen}(s^{5^k},s,w)$$

conjunction key

$$\mathrm{conj}\leftarrow \mathbf{SwitchKeyGen}(s^{-1},s,w)$$

returns

$$(\mathrm{pk},\mathrm{rlk},\{{\mathrm{rot}}_k{\}}_k,\mathrm{conj})$$ $$\mathbf{SwitchKey}(d\in R_{Q_{\ell }},{\mathrm{swk}}_{s\to s^{\prime }})$$

基底
$w$
s.t.

$$d=⟨\mathbf{d},\mathbf{w}⟩$$

returns

$$(d_0,d_1)=\lfloor P^{-1}\cdot ⟨\mathbf{d},{\mathrm{swk}}_{s\to s^{\prime }}⟩\rceil (\mathrm{mod}{Q}_{\ell })$$ $$\mathbf{Rotate}(\{\mathrm{ct},Q_{\ell },\Delta )\},k)$$

$\mathrm{ct}=(c_0,c_1)$
returns

$$\{(c_0^{5^k},0)+\mathbf{SwitchKey}(c_1^{5^k},{\mathrm{rot}}_k),Q_{\ell },\Delta \}$$

2.2 CKKS Bootstrapping

レベル
$\ell =0$
の暗号文
$\mathrm{ct}=(c_0,c_1)$

$$\mathbf{Decrypt}(\mathrm{ct},s)=[c_0+c_{1}s{]}_{Q_0}=\mathrm{pt}$$

bootstrappingの目標は

$${\mathrm{ct}}^{\prime }=(c_0^{\prime },c_1^{\prime })$$

(レベル
$L-k>0$
,
$k$
: bootstrap回路の深さ) を計算すること. ここで,

$$[c_0^{\prime }+c_1^{\prime }s{]}_{Q_{L-k}}\approx \mathrm{pt}$$ $$[c_0+c_{1}s{]}_{Q_L}=\mathrm{pt}+Q_0\cdot I$$

, (
$I$
: 整数係数多項式) より, bootstrappingはCRT基底の拡張に相当(?).
そして, 同型で
$\mathrm{mod}{Q}_0$
する.
最初のbootstrappingでは

1. 同型でencoding演算を計算

$$\mathbf{Encode}(pt+Q_0\cdot I)={\mathrm{pt}}^{\prime }$$

2. 各slotでscaled 近似sin関数を評価

$$\frac{Q_0}{2\pi }\sin \frac{2\pi {\mathrm{pt}}^{\prime }}{Q_0}={\mathrm{pt}}^{\prime \prime }$$

3. decoding

$$\mathbf{Decode}({\mathrm{pt}}^{\prime \prime })\approx \mathrm{pt}$$

modular reductionを試みた.
Cooley-Tukey アルゴリズムを準同型演算してEncodingを計算(深さは
$\mathcal{O}(\log n)$
)
encoding行列を
${\log }_{r}n$
個のスパースな行列を因数分解する手法により2桁高速化
またチェビシェフ補間でサイン関数の近似を改善
最近ではCKKS-full RNSにbootstrapを移植
中間的なRNS分解でkey-switchingを一般化した.
平文の大きさを考慮して余弦関数と二重角で3倍高速化
HEAANで実装されている.

2.3 Security of Sparse Keys

これらはハミング重み
$h=64$
のスパースな秘密鍵を使用している
$h$
の小さい鍵を用いることで深さの浅いbootstrapが可能になり実用性高まる.
近年のRLWEの安全性研究ではスパースな鍵が安全性に影響を与えることが知られている.
それを考慮すると
$h=64,N=216$
の時
$\lambda =128$
にするには
$\log Q=990$

3. Homomorphic Polynomial Evaluation

3.1 The Baby-Step Giant-Step Algorithm

baby-step giant-stepアルゴリズム 参照

3.2 Errorless Polynomial Evaluation

BSGSアルゴリズムより高精度で多項式の評価をすることができるアルゴリズム
BSGSの準同型評価版みたいな?
$c$
などの係数はRNS表現だから行列になっている?
多項式の $p(t)$ の評価においてrescalingでの誤差に対処する.
葉の単項式 $u_{i,2^I}(t)$ が全て同じスケール
$\Delta$ での加算で評価されるように葉の単項式をスケールする.

$$u_{i,2^{j+1}}(t)=u_{i+1,2^j}(t)\cdot T_{2^j}(t)+u_{i,2^j}(t)$$

単項式評価の結果
$u_{i+1,2^j}(t)$
のスケールを
${\Delta }_{u_{i,2^{j+1}}}(t)$
$T_{2^j}(t)$
のスケールを
${\Delta }_{T_{2^j}(t)}$
$q_{T_{2^j}(t)}$
は

$$u_{i+1,2^j}(t)\cdot T_{2^j}(t)$$

をリスケールしたもののモジュラス

3.3 Depth-Optimal Polynomial Evaluation

4. Key-switch and Improved Matrix-Vector Product

key-switchは公開鍵の操作の一般的な操作.
秘密鍵 $s$, $s^{\prime }$ から特定の公開鍵のkey-switch keyが作られる.
影響をキャンセルするために殆どの準同型演算でkey-switchingが必要になる.
特に準同型乗算では $s^2$ を $s$ に戻す必要があり, 回転演算では 回転された $s$ を $s$ に戻して再暗号化する必要がある.
key-switchはNTT, CRTを再構成するので重い.
4.1 で最適化されたkey-switchの鍵方式とアルゴリズムを提案
4.2 では hoisted-rotationを改良. そして, 4.3 で改良されたvec-mat演算を示す.

4.1 Improved Key-Switch keys

Supplementary Material B: KeySwitch Approaches

暗号文

$$(c_0,c_1)=(-a{s}^{\prime }+m+e,a)$$

($s^{\prime }$ で復号できる)
key-switch鍵

$$\mathrm{swk}=(-bs+s^{\prime }+e^{\prime },b)$$

$s^{\prime }\to s$
にkey-switchするとは

$$(c_0,0)+c_1\cdot \mathrm{swk}=(-a{s}^{\prime }+m+e,0)+(-abs+a{s}^{\prime }+a{e}^{\prime },ab)=(-abs+a{e}^{\prime }+m+e,ab)$$

$a{e}^{\prime }$
は大きな誤差なので復元時にずれる. これに対して2パターンの解決策がある.

Type 1

$${\mathrm{swk}}^{(i)}=(-b_{i}s+w^{(i)}{s}^{\prime }+e_i^{\prime },b_i)$$

$w$ を基底(?) として $c_1$ を分解する.

$x=\sum x_w^{(i)}{w}^{(i)}$ とすると

$$(c_0,0)+\sum c_{w,1}^{(i)}{\mathrm{swk}}^{(i)}$$

を計算.

$$=(-a{s}^{\prime }+\sum a_w^{(i)}{e}_i^{\prime }+m+e,a^{\prime })$$

になる(なぜ?)

Type 2

$$\mathrm{swk}=(-bs+P\cdot s^{\prime }+e^{\prime },b)$$

($P\approx \Vert a{e}^{\prime }\Vert$ 巨大な数) 計算,

$$(c_0,0)+\lfloor P^{-1}\cdot c_1\cdot \mathrm{swk}\rceil =(-a^{\prime }s+\lfloor P^{-1}\cdot a{e}^{\prime }\rceil +m+e,a^{\prime }$$

)
となり,
$\lfloor \cdot \rceil$
はnegl (式変形なぜ?)
ハイブリッドなアプローチもある, より大きなパラメータに適している. key-switchingがとても効率的になった
モジュラス
$Q_L={\prod }_{j=0}^L{q}_j$
が与えられ,

$$\left({\mathrm{swk}}_{q_{{\alpha }_i}}^0,{\mathrm{swk}}_{q_{{\alpha }_i}}^1\right)=\left({\left[-a_{i}s+s^{\prime }\cdot P\cdot \frac{Q_L}{q_{{\alpha }_i}}\cdot {\left[{\left(\frac{Q_L}{q_{{\alpha }_i}}\right)}^{-1}\right]}_{q_{{\alpha }_i}}+e_i\right]}_{P{Q}_L},{\left[a_i\right]}_{P{Q}_L}\right)$$

5. Bootstrapping for the Full-RNS CKKS Scheme

• CKKS SchemeのBootstrapは誤差を減らすのではなく暗号文の係数を高いレベルにリセットすること
• $\{\mathrm{ct}=(c_0,c_1),Q_0,\Delta \}$ は $n$ スロットの暗号文
  • s.t. $\mathrm{Dec}(\mathrm{ct},\mathrm{s})=c_0+s{c}_1=\lfloor \Delta \cdot m(Y)\rceil +e\in \mathbb{Z}[Y]/(Y^{2n}+1)$
• bootstrap後: $\{\mathrm{c}{\mathrm{t}}^{\prime }=(c_0^{\prime },c_1^{\prime }),Q_{L-k},\Delta \}$
  • s.t. $\mathrm{Dec}(\mathrm{c}{\mathrm{t}}^{\prime },\mathrm{s})=c_0^{\prime }+s{c}_1^{\prime }=\lfloor \Delta \cdot m(Y)\rceil +e^{\prime }\in \mathbb{Z}[Y]/(Y^{2n}+1)$
• $e^{\prime }$ はbootstrap回路の評価で $e$ より増える

ModRaise

CRTmap: $R_{q_0}\to R_{q_0}\times \cdots R_{q_L}$ を $\mathrm{ct}$ に適用して $Q_L$ にする

$$[c_0+s{c}_1{]}_{Q_L}=Q_0\cdot I(X)+\lfloor \Delta \cdot m(Y)\rfloor =m^{\prime }$$

参考文献

• paper