FHE コンパイラ

FHE プログラムを書く際の煩雑さ（rescale / modulus switching の挿入、暗号パラメータ選択、SIMD batching）を自動化するコンパイラ。専門家でも手作業では難しい最適化を肩代わりする。

なぜ必要か

CKKS では加減算は scale と modulus が一致していないと評価できず、乗算後に rescale を入れないとノイズが指数的に増える。RNS 実装では rescale に使える素数が限られ挿入位置の選択が複雑。さらに最適なrelinearize配置は NP-Hard。これらを隠蔽するのがコンパイラの役割。

主要なコンパイラ

• EVA (Microsoft): 暗号化ベクトル演算の DSL / 中間表現。Abstract Semantic Graph 上で rescale・mod-switch・relinearize を最適挿入し、パラメータと回転鍵を自動決定。SEAL をバックエンドに。後続の EVA Improved は Total Sum の batching を最適化。
• CHET (Microsoft): ニューラルネット推論特化。Homomorphic Tensor Circuit と HISA の 2 段中間表現を持ち、データレイアウト選択とプロファイルガイド付き scale 決定で手チューニングを自動化（18h → 5min）。
• HECO: ループや要素アクセスを書ける高水準言語を SIMD バッチ演算へ自動変換。要素単位の演算をベクトル全体の演算に置換し、fold パターンを $O(\log n)$ 回転に削減。MLIR 上に構築、naive 比最大 3500 倍。
• HECATE: scale と modulus を型システムに組み込み、rescale タイミングを最適化（MLIR）。
• 先行: Ramparts、Cingulata/Armadillo、ALCHEMY、Google FHE Transpiler。

最適化の階層

1. プログラム変換（高水準 → SIMD）
2. 回路最適化（乗法的深さ削減）
3. 暗号最適化（rescale / mod-switch 挿入、パラメータ選択）

SoK によれば、SIMD をどれだけ活かせるかが数桁の性能差を生む。サーベイ・分類は SoK を参照。関連クラスタ: _moc-crypto

乗法的深さと回路最適化

FHE の性能を支配する 2 つの量と、それを削減する回路最適化技法。

乗法的深さ (multiplicative depth)

乗算ごとにノイズが増え modulus chain のレベルを消費するため、回路の乗算の連鎖の最大長が必要パラメータ（$N$, $Q$）と速度を決める。

$$l(v)=\underset{n\in c(v)}{\max }l(n)+\{\begin{array}{ll}1& (v.\text{op}=\times )\\ 0& (\text{otherwise})\end{array}$$

加算は深さを増やさないので、式を再構成して乗算木を浅くするのが効く。multiplicative complexity（必要な AND/乗算の総数）も別軸の最適化対象で、ブール回路では論理合成ツールボックスや cone rewriting、multi-start ヒューリスティックで削減する。量子回路の T-depth 削減とも同型の問題。

SIMD batching と回転

• CRT パッキング: 中国剰余定理 $\mathbb{Z}/mn\cong \mathbb{Z}/m\times \mathbb{Z}/n$ により、平文多項式を複数 slot に分解して $N/2$ 並列演算。
• 巡回シフト: slot の回転は多項式の自己同型 $X\mapsto X^k$ で実現できる（“なぜ FHE で巡回シフトが出来るのか”）。回転鍵が必要。
• hypercube 構造: slot を多次元立方体とみなし、次元ごとの回転で任意の置換を組む。

線形変換と行列積

行列ベクトル積は線形変換として暗号化したまま評価できる。対角ベクトルでグループ化する方式や、BSGS（baby-step giant-step）で回転回数を $O(\sqrt{n})$ に減らす手法が定石。機械学習の MatMul を FHE 上で速くする鍵となる。

これらの最適化を自動化するのが fhe-compiler。関連クラスタ: _moc-crypto

選択多項式

著者自身の研究テーマ。準同型暗号（FHE）の暗号文ベクトルに対する演算を多変数多項式で表し、最小コストの命令列へ分解する問題を定式化したもの。AMRG 演算の一般化として「暗号文から要素を選択する」ことから名付けられた。

動機と定義

FHE では暗号文ベクトルに対する基本演算が

• Add: $R=P\oplus Q$
• Mult: $R=P\odot Q$
• Rotl: $R=P\ll k$（巡回シフト）

に限られる。暗号文の組 $X$ に対する演算結果は多変数多項式ベクトル $\mathbb{R}[X{]}^N$ で表せ、これを選択多項式と呼ぶ。任意の選択多項式は単位選択多項式（1 つだけ非零の 1 変数 1 次）の線形結合に分解できる（自明な分解）。

演算コストの最小化

同じ多項式でも分解の仕方でコストが変わる。例 $[x_1+x_2+x_3,0,0]$ は

• 自明な分解：2 add, 3 mult, 6 rot
• 最適な分解 $(x\oplus (x\ll 1)\oplus (x\ll 2))\odot [1,0,0]$：2 add, 1 mult, 3 rot

そこで「多変数多項式ベクトル $V$ が与えられたとき、演算コスト最小の和分解 ${\sum }_i{W}_i$ を求める」最適化問題を定式化する。各 $W_i$ は all-same / diagonal-same / single-nonzero / all-zero のいずれかの制約を満たすものとし、回転コスト $c_{rot}$・マスクコスト $c_{mask}$・加算コスト $c_{add}$ を目的関数に置く。

関連する道具と未解決点

• 演算は置換マスク行列 $M\cdot v+C$ で表せ、置換 $\tau$ と置換行列 $T$ の対応の拡張になる。rotl は連続巡回置換で、その分解は巡回シフトが生成する置換の知見が必要。
• ソルバによる最適解探索、E-graph（egg）による自明な分解からの再結合、計算グラフ最適化との類似が検討されている。
• 行列積 matmul を line/col/get_index/set_index の合成 $A\cdot B={\sum }_k(\sigma \circ {\varphi }^k)(A)\odot (\tau \circ {\psi }^k)(B)$ として導出・検証している。
• 関連手法としてRNS、グレブナー基底や有限体算術回路検証を参照。

関連: number-theoretic-transform / computability-theory / _moc-crypto