EVA: An Encrypted Vector Arithmetic Language and Compiler for Efficient Homomorphic Computation
1. Introduction
- CKKS scheme とか乗算でノイズ増えないようにReScalingを手動でやる必要
- 暗号化ベクトル演算(EVA) というFHE用の汎用言語を提案
- EVAは他のDSLコンパイラのバックエンド(中間表現)となるようにも設計されている
- 固定幅ベクトルとスカラーの演算をサポート → SIMDとかで最適化
- 複雑なスキームのコンテキストを隠している
- ReScalingとかmodulus-switchingを最適に挿入
- EVA用のPythonフロントエンドも実装して機械学習とか画像認識(Harrisのコーナ検出)アプリケーションを実装してみた
2. Background and Motivation
2.1 FHE
- schemeがある
- Ring-LWE 上に構築されている
- 積和ができる
- batching: 演算のsimd性
- batchingができるschemeはrotationができる(回転鍵と呼ばれる公開鍵が必要)
2.2 Challenges in Using FHE
- mult depth
- 回路が深くなると複合できなくなる
- Relinearization: 暗号文の乗算は3つの多項式 → 2つにする(タイミングを最適化するのはNP-Hard)
- CKKSと近似固定小数点(Q小さく保つ&&誤差切り上げるためにReScaling) (要: 同レベルの暗号2つ)
- 準同型暗号の専門家でも適切な ReScaling と modulus-switching を挿入するのは困難なプロセス
- RNS表現を用いた実装ではReScalingに使えるQ’ はひとつだけ → ReScalingする場所の選択が複雑
- 暗号化パラメータの選択が困難
- パラメータに関連して, scaleが決まる
2.3 SEAL
2.4 Threat Model
3. EVA language
Types and Values
Cipher固定小数点のリストVectorVec<f64>Scalarf64Integeri32
concat を ++ と書く,
Instructions
NEGATE: C -> CADD: C -> C -> CSUB: C -> C -> CMULT: C -> C -> CROTATELEFT: C -> I -> CROTATERIGHT: C -> I -> CRELINEARIZE: C -> CMODSWITCH: C -> CRESCALE: C -> S -> C
Execusion Semantics
適当な暗号スキーム id を考える。Cipher に Vectorの値そのまま入れる. つまり Encrypt と Decrypt は identity
ProtoBufなシリアライズ表現を使用している(言語に依存しない)
- EVAのOpcodeとRNS-CKKSスキームとは一対一の関係があるが直接実行することは出来ない → 暗号化パラメータとの兼ね合いで実行時に例外がthrowされるかも
- すべてのRNS-CKKSのCiphertext の係数は mod q: vec, Q = \prod q とする
- スケールはそれに関連している
- ちなみにSEALは q_i は2の累乗に近い素数 → 2の累乗として扱う
SEALでは、係数係数qiが2のべき乗に近い素数であれば、その係数qiは2のべき乗に対応すると仮定します。EVAコンパイラ（およびこの論文の残りの部分）では、qiが2乗に近い素数であると仮定しています。この矛盾を解決するために、RESCALE命令がスケールを素数で割ると、スケールは2乗で割ったように調整されます。
前提: scaleもmodulusも小さいほど計算早い → 効率
- 変数にスケール(合わせるためにReScaling)とモジュラス(合わせるためにMod-Switching)がある
4. Overview of EVA Compiler
4.1 Using the Compiler
4.2 Motivataion & Constraints
- +, -, *: modulusが同じ
- +, -: scaleが同じ
効率化の流れ
-
具体例
-
(a) 普通にやるとQ = 2^210 以上となる
- まず毎回掛け算の後にrescale入れる
-
(b) はmodulus制約満たしてない: 2^30 * 2^60 は出来ない
-
(c) のようにmod-switch入れて2^60 → 2^30 にする
-
(d) Q = 2^150 以上なので改善出来ている
-
命令の制約が原因で発生する複雑さの例
Ciphertext (scale: )の式 を計算することを考える
(b) だと Q = 2^60+, scale = 2
x^2 のscaleは s_x^2 となりスケールが合わないので計算できない
→ より高い方に合わせるため 1(scale: s_x) を x にかけると
x^2(s_x) + x(s_x) * 1(s_x) となり計算可能
しかしこれだと暗号文のスケールとノイズが指数関数的に増加してしまう
(c) も 2^60+ だが modulusの長さ r が違うので 小さい r 選べば(c) のほうが効率的 scale = 2^60 だからおそくなるのでは
(??? rescale ないから?)
出力のスケールは にしたいとする
→ rescale で低く保つ
rescale(x^2) + x = (s_x)
- Rescale命令を挿入するとおかしくなるかも
- rescale(x^2) + modswitch(x) で解決(????)
掛け算には違う制約もある
k poly * l poly = (k + l + 1) poly となるので
掛け算の上のノードはなるべく増やしたくない
をrescaleすると最大値とする(SEAL: s_f = 2
これらの制約を満たしながらライブラリを使うのは大変
要約すると、FHE スキーム(またはライブラリ)は、すべての暗号制約のため、プログラマが推論するのは面倒です。プログラマーは、性能を最適化する方法で制約を満足させることは、さらに厄介なことです。EVA コンパイラはこのような暗号の詳細をプログラムマーから隠し、プログラムを最適化します。
4.3 Execution Flow of the Compiler
- EVA コンパイラは式を Abstract Semantic Graph で表現(以下 graph)
- コンパイラはこのグラフを変換、検証、パラメータ選択、回転選択をしながら最適化していく
- 検証しているので実行時は絶対制約違反しない
- 変換はsection5で説明
- 最後に出力プログラムに対して暗号化パラメータとRotationKeyのためのビットサイズとかを決定
- (グラフは変わらないよ) Section6で説明
5. Transformations in EVA Compiler
これが書き換え規則です
5.1 Graph Rewriting Framework
-
step1: forward pass 親を書き換えた後子を: 上から下に
-
step2 backward pass 下から上に書き換える
-
6つの最適化がある
-
EAGER-MODSWITCH: backwardのみ → 先やる
-
WATERLINE-RESCALE
-
EAGER-MODSWITCH
-
MATCH-SCALE
-
RELINEARIZE
5.2 Relinearize Insertion Pass
- RELINEARIZE
- すべてのCiphertextは2+の多項式で表されている
- 2多項式の暗号文どうしの掛け算で3つの多項式になる relinearizeで2つに
- 最適な配置を考えるとNP Hard なのでシンプルに常に2になるように
5.3 Rescale and ModSwitch Insertion Passes
formalにinsertionを書いている
- +, * の親はすべてmodulusを同じにしなければならない
- N, r が大きいとコストが高くなる
6. Analysis in EVA Compiler
7. Frontends of EVA
8. Experimental Evaluation
- CHET との比較
- latency
- HE kernels
- 3d path length
- linear regression
- polynomial regression
- multivariate regression
- sobel filter detection
- harris corner detection