Faster homomorphic encryption is not enough

Faster homomorphic encryption is not enough: improved heuristic for multiplicative depth minimization of Boolean circuits

Abstract

• SHE（e.g. BFV scheme, BGV scheme): 暗号文のサイズと演算の実行性能は、乗算深度に大きく依存します
  • 乗算深さとは，同型の暗号化方式がパラメータ化されている連続した乗算の最大数のことである．
• 本研究では、改良された乗算深度最小化ヒューリスティックな手法を提案します
  • 具体的には、新しい回路書き換え演算子(円錐書き換え演算子)を導入する
• より小さいブール回路のベンチマークにおいて、文献にある先行研究と比較して
  と比較して、より小さな乗算深度が得られました。平均して、乗算深さは大幅に改善され、新しいヒューリスティックの実行時間は時間が大幅に短縮されました
• 提案された書き換え演子とヒューリスティックは、ブール演算回路に限らず、算術演算回路にも使用可能です

Keywords

• Somewhat homomorphic encryption
• Multiplicative depth
• Boolean functions · Heuristic

Introduction

• Bootstrap Problem(bootstrap数を最小化する) 研究はいくつかある
• ハードウェア合成の問題では回路面積やレイテンシを最小化するための回路最適化アルゴリズムはあるが, FHEの乗算回路に対応したものはない
• Faster Fully Homomorphic EncryptionBootstrapping in less than 0.1 Seconds などではブール回路のANDゲート数を最小化する研究

A multi-start heuristic for multiplicative depth minimization of boolean circuits

• A multi-start heuristic for multiplicative depth minimization of boolean circuits

• Singulataの作者は multi-start priority based heuristic [9] based on multiplicative depth-2 path rewriting operators.

• 平均して乗算の深さを3倍以上に減らすことができた

• 基本的なヒューリスティックを異なる優先度で何度も実行するためアルゴリズム全体のコストはとても大きくなる

• 結局すべてのベンチマーク回路の深さを最小にすることは出来なかった

• ランダムな優先度関数の方が非ランダムよりよい結果が得られることもあった

• 本論文では A multi-start heuristic for multiplicative depth minimization of boolean circuits multiplicative depth-2 path rewrite operator コーン書き換え演算子として一般化する.

2 Rewrite Operators

2.1 Preliminary definitions

ブール回路はDAG $C=(V,E)$ として, ノードは３種類に分けられる.

• 親のないノードは 入力: $C_i$ bool(定数 or 変数)

• 子のないノードは 出力 $C_o$

• 演算ノード: AND か XOR のみ(これですべてを表現できる)

• pred: V -> 2^V , succ: V -> 2^V はそれぞれのノード $v\in V$ の親, 子を返す関数

• anc: V -> 2^V, desc: V -> 2^V は祖先, 子孫を返す関数

• mult-depth の削減は鍵長の削減だけでなく実行コストも下げる

関数 $d:V\to \{0,1\}$ : ANDノードなら1, それ以外なら0 を返す.

回路のmult-depthは最大の乗法的深さのパスになる.

回路の乗法的深さを $l:V\to \mathbb{N}$ で与える

l(v) = 0 if |pred(v)| = 0 else max_{u \in pred(v)} l(u) + d(v)

reverse multiplicative depth: r(v) は pred を succ に変えたもの(=それより子孫のmult-depth)

回路全体のmult-depth $l^{\max }={\max }_{v\in V}l(v)={\max }_{v\in V}r(v)$

critical circuit $C^{\ast }$: critical nodes が含まれている回路(critical pathも同様)

critical cone: critical nodeにつながっている先祖達

2.2 Multiplicative depth-2 path rewriting

• A multi-start heuristic for multiplicative depth minimization of boolean circuits では２つの書き換え演算子を組み合わせてmult-depth を削減しました.
  • 私達はそれを改良し一つの演算子にします. 紹介します.

$p=(v_1,U_y,v_t)$ はANDゲート $v_1$ から ANDゲート $v_t$ までのパス

その中には multi-input XORゲート $U_y$ が入力 $v_1,y_1,\cdots y_m$ を持っている.

(一般性を損なわないように，最初の回路の中間的な2入力XORゲートを，1つの多入力XOR
ゲートにまとめました)

$v_1$ の入力 $a_1,a_2(l(a_1)\ge l(a_2))$, $a_3$ は $v_t$ の入力, その他は $U_t$ の入力(図1右, 太線はcritical path)

$p$ を論理式にすると $((a_1\cdot a_2)\oplus {⨁}_i{y}_i)\cdot a_3$

これを $((a_2\cdot a_3)\cdot a_1)\oplus (a_3\cdot {⨁}_i{y}_i)$ にしたい.

$a_1$ から $r$ までの局所的なmult-depth は1減っている(まあそう)

→ critical path変わらないのか？

$mi{n}_{u\in pred(v)}l(u)<l(v_1)-1,v\in \{v_1,v_t\}$

(2)

が成り立っているなら

mean: v_1, v_tは子孫がANDが1個より少ない=v_1, v_tがANDノードであればいい

multi-input XORゲートは書き換えた後ツリー状に並び替えることで２入力ゲートを得られる(順不同).

特殊な例について説明する.

もし, パス $p$ が一つもXORノードを持っていないとき変形結果は $(a_2\cdot a_3)\cdot a_1$ になる.

もし, $U_y$ が2入力XORゲートなら消え,m ANDゲート $u_y$ は$y_1$ と $a_3$ を入力とする.

• 変形後のmult-depth $l(r)=l(a_1)+2$, (2)が成り立つなら

$r=\max (l(a_1),l(y_1),\cdots l(y_m))+1$

になる.

ノード y_i(i = 1..m) が変換前にcritical pathの上にあるならmult-depth は保たれる

→減らせない

$r$を$l(a_1)+2$から $l(a_1)+1$に減らすために 少なくとも1回別の$u_y$で終わる別のdepth-2path writingが必要(例えば図左側)

$y_1$がcritical-path上にあったらdepthは変わらず

critical-pathに属しているU_yの各入力に対してpath-rewritingが必要になるから

9]の著者は，中間ノードy_1 .. y_m の mult-depth 2のパスの特殊なケースのみを研究した.
このため，この演算子の適用範囲は狭く，また，パスの書き換え回数を減らすために必要な
演算子の適用範囲が限定され，乗算深さを減らすために必要なパスの書き換え回数も限定される．

2.3 Multiplicative depth-2 cone rewriting

Multiplicative depth-2 cone rewriting 参照

• 1回の適用では全体の乗算深度が減少しない場合がある

• のでこの問題を解決するために、乗算深さ2のパス演算子を乗算深さ2の円錐形に一般化

• $y1,\cdots ,ym$ のサブセットのうちクリティカルなノードから回路を上方に走査

  • 最初に見つかったANDゲートで停止

• このようにして、乗法的深さ2の円錐が得られる。

以下ではこのような円錐を書き換えて，全体の乗法深さが減少するような書き換える方法を紹介します。

円錐形の書き換え演算子は、前述したように、

• XORゲート $U_y$ のcritical inputに対して、深さ2のパス書き換え演算子を適用することと等価
• 変換後に新たに生成されるノードの数を減らすことを目的

まず, 乗法深さ2のConeのための変換を提示し, それを任意深さの円錐に一般化

mult-depth 2の critical cone ${\delta }^2$

• ANDゲート $v_t$ で終わり、ANDゲート $v_1,\cdots ,v_n(v_i\in \mathrm{anc}({\mathrm{v}}_{\mathrm{t}}))$ で終わる

• $l(v_i)=l(v_t)-1{(}^{\forall }i=1,\cdots ,n)$

• $v_1,\cdots ,v_n$ の出力はXORゲート $U_y$ によって結合され, $v_t$ の1入力となる

• もうひとつの入力は $a_t$

• $a_1^{(i)},a_2^{(i)}(s.t.l(a_1^{(i)}))\ge l(a_2^{(i)}))$ を $v_i$ の2入力とする.

• $U_y$ の入力 $y_1,\cdots ,y_m$ はCriticalではない

• 式にすると $({⨁}_{i=1}^n(a_1^{(i)}\cdot a_2^{(i)})\oplus {⨁}_{i=1}^m{y}_i)\cdot a_t$

• 変換後は $({⨁}_{i=1}^n(a_t\cdot a_2^{(i)})\cdot a_1^{(i)})\oplus (a_t\cdot {⨁}_{i=1}^m{y}_i)$

• この変換によってANDゲート $u^{(i)}=(a_2^{(i)}\cdot a_t)\cdot a_1^{(i)}$ はmult-depthが下がった

• $U_y^{\prime }$ はcritical inputs を持たない

• $r$ のmult-depthは1下がった

${\min }_{u\in \mathrm{pred}(v_k)}l(u)<l(v_t)-2{,}^{\forall }{v}_k,k\in \{1,\cdots ,n,t\}$ … (3)

を満たすとき mult-depth は削減できる

2.4 Cone Rewriting

mult depth-2 cone rewrite は cone nodes に 制約 (3) が必要 (i.e. 最低でも一つの入力ノード $v_i$ は non-critical じゃないと行けない)

もしどちらもcriticalのとき, cone は $a_1^{(i)},a_2^{(i)}$ から始まり mult depth-3 cone を見つけられる

削減のルールを守れていればmult depth は削減出来るので mult depth が 3以上のときにも容易に拡張出来る.

そのような cone を構築するアルゴリズム ConeRec を示す

AND node: 少なくとも1つの pred が削減可能であればそれの pred に対応する cone が追加される(どちらも還元可能な場合はランダム)

XOR node: 両方のpredが削減可能なら結果に加える

総括すると, AND nodeはその少なくともひとつの先祖が削減可能で,

XOR nodeは両方の先祖が削減可能なら削減可能(???)

返り値のconeはreducableなことが保証されている.

我々は minDepth は l(p) + 1 を使用(p は v の入力のcriticalじゃない方)

次章では mult depth を減らすヒューリスティックな方法を紹介します.

3 Improved heuristic

3.1 Overview

• A multi-start heuristic for multiplicative depth minimization of boolean circuits では mult depth-2 path rewriting operator に基づく multi-start heuristic を提案した.
  • 彼らのヒューリスティックな手法は、優先順位関数を用いて、削減すべきmult depth-2のパスを選択しています。
• ブール回路の構造が、どの優先度関数が最も適切かということに重要な役割を果たしているようです。
• なので, 彼らは複数の優先度関数で最適化を実行して一番いいのを出力していました.(コスト大)
• アルゴリズム2(提案アルゴリズム)は、与えられたブール回路の乗算深さを1回の処理で最小化することを目的としています.
• 各反復において、最小化すべきconeの集合 ${\Delta }^{\min }$が計算されます。
• depthが改善されたら $C_{out}$ が更新される

Cone selection method

cone 選択手法は書き換えるべき最小の coneの集合を見つけること

書き換えはnodeの数を増やすのでそれを抑えることにもなる

そのためには

$C$ の各クリティカルパスは ${\Delta }^{\min }$ から最低一つのconeの終端ノードを含む

ので ${\Delta }^{\min }$ のconeを書き換えたあと全体のmult-depthが必ず減少することが保証される.

この問題は組合せ最適化の分野で DVD問題(Dag vertex deletion problem) [19] として知られている.

この問題は UG-hard です. = 指数時間かかる

cone 選択ヒューリスティックは

まず CONEREC を使ってすべての削減可能な cone の集合 $\Delta$ をみつける

グラフ $C^{\mathrm{AND}}$ (critical な ANDを含む) を作る

その間に深さ2の
クリティカルパスが存在する場合2つのANDノードがCANDで接続されています

もし, ANDノードが削減可能なcritical pathなら

ネットワークから着想を得た

$C^{\mathrm{AND}}$ のすべてのノード $v$ はトポロジカル順に訪れる.

ノードとエッジのフローを頂点ごとに計算する

ノードのフロー $f^{+}(v)$: 入力辺のフローの合計 or 1

出力エッジのフロー $g^{+}(v,u),u\in \mathrm{succ}(v)$, 入力のフローが等分される

todo あとで理解し実装する

3.3 Reductions on non-critical circuits

$C^{\mathrm{AND}}$ に削減可能なconeが一つもないことがある.

それはこれ以上mult depthを削減出来ないわけではない

回路 $C$ のnon-criticalな部分を書き換えする.

そのような目的で $v$ の全ての祖先を含む部分回路 $C_v$ を作成する.

$C_v$ のcritical circuitを計算し, アルゴリズム2 を適用することで $v$ の mult depth を削減することが出来る.

その後, 新たに削減可能な $C$ のconeがあるかを検証し, 書き換えを行う.

4. 実験結果

EPFL Combinational Benchmark Suite. からbool回路を使用.

3タイプの回路がある arithmetic, random/control, very-large(数百万gate)

実験には10 arithmetic, と 10 random/control 回路を使用

回路には前もって最適化する(ABCコマンドの resyn2 と map (and-xor グラフを得るため)

A multi-start heuristic for multiplicative depth minimization of boolean circuits も同じベンチマーク使っているよ

CでABCのバイナリをヘルパーに使って実装

掛け算の深さが同じであれば、cavlcとpriorityとrouterのベンチマークでは、ANDノードの数が少なくなります。
sqrtとか遅すぎる, hypは48時間やった

• EPFL Benchmark(blif format)
  • GitHub - lsils/benchmarks: EPFL logic synthesis benchmarks
• ABC CLI
  • ABC: A System for Sequential Synthesis and Verification

4.2 Homomorphic execution acceleration

まず HE の complexity of multiplication operation の推定について

FV
scheme の深さと暗号文サイズの関係

回帰すると
$y=1.2215x^{2.0179}$

FV はmult-depthと鍵サイズが相関するのか?,

Conclusion

このヒューリスティックは更に改良可能

e.g.
mult-depth
の削減と新たに生成されるANDゲートの数のトレードオフをより正確に計算(各イテレーションで生成するANDゲートの予算を決めておく)

e.g. 2回のイテレーション(?) で生成するANDゲートの数を最小に

Stream Ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression
にはANDゲートが少なくXORゲートが多いFHEアルゴリズムの実装が

思ったこと

• Boolean回路のANDゲート, XORゲートをInterger回路のMult演算, Add演算に置き換えたヒューリスティックでも効果がでるのではないか
• Boolean回路でのANDゲートの占める割合よりMult演算が占める割合が少ない?ならあまり改善しない?
  • CKKS scheme とかにあるRot演算はどの立ち位置になるのか?