乗法的深さと回路最適化

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