EVA Improved

EVA Improved: Compiler and Extension Library for CKKS

2. Improved EVA

2.2 Making Passes Easy to Write

EVAはIRをループフリーなDAGとして書くことでパスを簡単に書けるように

2.4 Raw Type and Encoding Insertion

• ciphertextとplaintextに加えてraw(固定長ベクトル)を加えた
• 暗号文との演算時にencodeノードが挿入される

2.5 Common Subexpression Elimination

• CSE: 等価な部分式をメモ化する

畳み込み演算を2回呼び出すがline 5で同じ回転を行うがCSEにより最適化されるのでそのまま書けば良い

2.6 Reduction Balancing

$(a\cdot b)\cdot (c\cdot d)$ は $((a\cdot b)\cdot c)\cdot d$ よりも乗法深さが浅いのでよい
バランスの取れた2分木に戻すパス

3. EVA Extension Library

3.1 Why an Extenstion Library

内積を考えると回転と加算を行う

naive: $O(N)$ 回回転演算
opt: $O(\log N)$ 回転

3.2 Horizontal Sum

3.3 Vector and Matrix

• SEALベクトルよりEVAベクトルが小さい

EXLベクトル

任意の長さの配列を扱うとき例えば $N=1000000$ とだと処理に時間がかかりすぎるので複数のEVAベクトルに分割する.
計算も分割する、

行列を対角線に分割するというよく知られた方法で積を実装した

$$Av=\sum _{i=1}^m\mathrm{diagonal}(a,i)\cdot \mathrm{rot}(v,i)$$

3.4 Vector Size and Program Generators

EVAベクトルがSEALベクトルよりも小さいときはベクトルをrepeatして合わせるので冗長な計算になる

• Porcupine A Synthesizing Compiler for Vectorized Homomorphic Encryption はユーザの計算のベクトル化を支援する