選択多項式

著者自身の研究テーマ。準同型暗号（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-math