Ramparts: A Programmer-Friendly System for Building Homomorphic Encryption Applications
Abstract
- RampartsはJuliaでHE Applicationを開発する環境を提供
- 以下3つの特徴
- コンパイラによって回路の深さと乗算のレベル両方を押さえたHE回路を構築
- HEの専門家のようにHEの適切なパラメータを選択
- 入力値を自動でplaintextにencoding, データ変換を自動
類似研究としてCingulataがあるが、より効率的
レントゲン画像とかプライバシーとして重要な場合にFHEが使われる
HE Library がたくさんあるね HELib, PALISADE, SEAL
アプリケーションも iDASH
Crusible: 破綻しやすい
Juliaのメタプロ使った
アナリストが手元でコードを書いて、信頼できないサーバー上で計算して返す.
Juliaと同じIFで関数とかかけるが、FHEライブラリの演算に準拠しているので例えば比較とかは出来きません.
アーキテクチャ
- Juliaの式 → S式
- Crusibleで S式から回路に
- PALISADEに回路と暗号化された入力をわたす
回路サイズとかの最適かは従来は手動.
RAMPARTSはシンボリック実行(?) で自動化
回路構築と最適化の過程で
- sub-expression elimination, constant folding, 部分評価最適化
- 乗算回路を減らすように最適化
HEライブラリを使うときの難点
- Rampartsは回路の深さを自動的に抽出
- 入力データ構造がベクトルに変換するのもシームレスに(適切なエンコードを)
Frontend Processing
Fhe.jl というライブラリで提供
Fhe.keygen(scheme, [f, size]) BFVスキームかNULL(デバッグ用)
@Fhe.evaluate expr で実行
evaluateの方法
Fhe.evaluate(f, args)
- f の Julia IR をみて
symbolic expression(S式)に変換, Lisp みたいな形 - S式をCRUSIBLEに渡して, ループ展開や分岐除去、副作用除去をして回路の形にする. (§4.2 で詳しく)
- 回路と暗号化された入力をバックエンドに入力
- 結果を復号化&&Juliaの形式に
4.2 S式から演算回路の変換
S式をSSA形式に変換.
ループをアンロールするとDAGになり、これを演算回路に変換
+,-,*,>>, dotをサポート
4.3 高レベルな変換
S式にすると高レベルな最適化が使える.
ゲート選択(4.3.1) と回路レベルの最適化(4.3.2) について説明
例えばdot productを環と積で表すのではなく専用の命令がライブラリに用意されているならそちらを使う.
- 深さ最適化
Nの配列をループして合計出すときとかはlog N + 1 とかにできる → 木のバランスを取る