🤖 machine learning

CHEHAB RL: Learning to Optimize Fully Homomorphic Encryption Computations

本論文は、ベクトル化のための書き換え規則の適用を学習することで、完全準同型暗号コードの最適化を自動化し、その結果、最先端の手法と比較して実行速度の大幅な向上、ノイズ増加の抑制、およびコンパイル時間の劇的な短縮を実現する深層強化学習フレームワークであるCHEHAB RLを提案する。

原著者： Bilel Sefsaf, Abderraouf Dandani, Abdessamed Seddiki, Arab Mohammed, Eduardo Chielle, Michail Maniatakos, Riyadh Baghdadi

公開日 2026-01-28

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Bilel Sefsaf, Abderraouf Dandani, Abdessamed Seddiki, Arab Mohammed, Eduardo Chielle, Michail Maniatakos, Riyadh Baghdadi

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

大きな構想：「鍵のかかった箱」問題

想像してみてください。あなたは銀行のパスワードや医療記録のような、非常に価値のある秘密を持っています。それをクラウドサーバー（見知らぬ人）に送り、そのデータを使って何らかの計算をしてもらいたいと考えていますが、相手が中身を覗き見て秘密を盗むことを恐れています。

**完全準同型暗号（FHE）は、この問題に対する魔法のような解決策です。これは、データを「鍵のかかった透明な箱」**に入れるようなものです。あなたは、鍵を開けたり中身を見たりすることなく、その箱を相手に渡し、相手には箱を振ったり、叩いたり、中身を混ぜ合わせたり（計算を実行）させることができます。作業が終わったら、彼らは箱をあなたに返し、あなたはそれを開けて結果を確認します。

落とし穴： この魔法は、信じられないほど遅く、かつ厄介です。鍵のかかった箱に対して計算を行うことは、通常のデータに対して行うよりも何千倍も時間がかかります。それはまるで、厚手で不器用なオーブンミトンをはめたまま、ケーキを焼こうとするようなものです。

問題点：レシピを書くのが難しい

この「鍵のかかった箱」での計算を高速化するために、専門家は非常に具体的で低レベルなコードを書かなければなりません。それは、まさにそのオーブンミトンをはめたまま、ケーキのレシピを書こうとするようなものです。

複雑すぎる： データが混ざり合わないように、どのように箱の中に材料（データ）を詰め込むかを正確に決定しなければなりません。
遅すぎる： もし詰め方を間違えると、計算に膨大な時間がかかるか、あるいは箱の中の「ノイズ（静電気のようなもの）」が大きくなりすぎて、最終的な結果がゴミになってしまいます。
探索の罠： データを詰め込む完璧な方法を見つけることは、干し草の山の中から針を探すようなものです。既存のツールは、一つひとつの場所を一つずつチェックしていく（「総当たり」検索）ことで針を見つけようとします。これには長い時間がかかり、実際には最善ではない「そこそこ良い」場所に陥ってしまうことがよくあります。

解決策：CHEHAB RL（「賢い弟子」）

この論文の著者たちは、CHEHAB RLと呼ばれる新しいツールを開発しました。あらゆる可能性を一つずつチェックする代わりに、彼らはコンピュータに**「学習する方法」を教えました。これには強化学習（RL）**という手法が使われています。

これは、**「賢い弟子のシェフ」**を訓練することに似ています：

目標： 弟子の仕事は、計算が最も速く、かつノイズが最小限になるように、鍵のかかった箱の中の材料を並べ替えることです。
訓練： 弟子にルールブックを与えるのではなく、弟子が材料を並べ替える何百万通りもの方法を試させていきます。
- もし並べ替えによって計算が速くなれば、弟子には「ご褒美（報酬）」が与えられます。
- もし計算が遅くなったりノイズが増えたりすれば、「お叱り（ペナルティ）」が与えられます。
データセット： 弟子を教えるために、著者たちは単なるランダムなガラクタを使ったのではありません。彼らは、現実世界のコードで訓練された超スマートなAIである**大規模言語モデル（LLM）**を使用して、何千もの現実的な「練習用レシピ」を生成しました。これは、弟子にランダムな小麦粉や卵の山ではなく、本物のケーキで練習させているようなものです。

仕組み：「書き換え」ゲーム

このシステムの核心は、**レゴ（Lego）**のゲームです。

あなたには、レゴブロックで作られた構造があります（あなたの暗号化されたコード）。
あなたには、一連のルールがあります（例えば「この2つのブロックを入れ替える」や「この3つを1つに結合する」など）。
**RLエージェント（弟子）*は、その構造を見てこう判断します。「もしここでルールAを適用し、次にそこでルールBを適用したら、全体的により安定し、かつ高速になるだろうか？」*

エージェントは、これらのルールを最適な順序で適用するための**ポリシー（戦略）**を学習します。単に一つのステップを見るのではなく、全体像を見て、最善の経路を見つけ出します。

結果：スピード、静寂、そして効率性

論文では、彼らの「賢い弟子（CHEHAB RL）」を、現在最高峰のツールである「Coyote」と比較しています。結果は以下の通りです。

実行速度（ケーキの焼き方）： CHEHAB RLが生成したコードは、Coyoteよりも5.3倍速く動作しました。それは、遅い手動のオーブンから、高速のコンベクションオーブンに切り替えたようなものです。
ノイズ（静電気）： 鍵のかかった箱の中の「ノイズ」の増加量は、CHEHAB RLを使用した場合、2.54倍少なくなりました。これは、最終的な結果がよりクリアになり、台無しになる可能性が低いことを意味します。
コンパイル時間（レシピの作成）： おそらく最も驚くべき結果は、Coyoteが探索を行うのにかかった時間よりも、CHEHAB RLが最適化されたコードを書くのにかかった時間の方が、27.9倍も短かったことです。弟子は戦略を素早く学習しましたが、Coyoteはまだ干し草の山を必死に探し回っていました。

なぜこれが重要なのか

この論文は、この特定のFHEコードの最適化問題を解決するために、強化学習が使用された初めての事例であると主張しています。

乱れたコードにも対応： ループ構造に基づいた整然としたコードにしか機能しない古いツールとは異なり、このシステムは、絡まった毛糸玉のような、構造化されていない乱れたコードも扱うことができます。
スケーラビリティ： 問題が大きくなるにつれて、「賢い弟子」はより上手く対処できるようになりますが、従来の「総当たり」検索手法はどんどん遅くなっていきます。

まとめとしての比喩

あなたが、ガラスケースに閉じ込められた膨大な数の本がある巨大な図書館を整理しようとしていると想像してください。

従来の方法（Coyote）： あなたは、本の配置がどれだけ速く見つけられるかを確かめるために、あらゆる配置を試そうとする司書チームを雇います。彼らは疲れ果て、長い時間がかかり、結局は「そこそこ良い」配置を選んで終わってしまいます。
新しい方法（CHEHAB RL）： あなたは、他の図書館がどのように整理されているかの動画を何千本も見てきた、天才的な司書を雇います。彼らは、何がうまくいくのかという「パターン」を学びます。新しい図書館を渡されたとき、彼らは瞬時に最適な整理方法を知っており、わずかな時間で、かつ本をより見つけやすく整理してくれます。

この論文は、「学習」というアプローチを用いることで、この「鍵のかかった箱」の技術をより実用的なものにし、結果を待つのに何日も費やすことなく、プライベートなデータに対して複雑な計算を行うことを可能にすると結論付けています。

技術要約: CHEHAB RL: 完全準同型暗号計算の最適化のための学習

1. 問題提起

完全準同型暗号（FHE）は、データのプライバシーを維持したまま、復号することなく暗号化されたデータ上での計算を可能にする。しかし、FHEは依然として計算コストが高い。例えば、暗号文の乗算は、そのプレーンテキスト版と比較して $10^6$ 倍遅くなることがある。この性能差は、高次多項式の乗算や大幅なノイズ増加を伴う、同型演算固有の複雑さに起因している。

効率的なFHEコードを書くことは、深い暗号学的専門知識を必要とする複雑でエラーが発生しやすいタスクである。FHEコード生成を自動化するためにコンパイラが開発されてきたが、既存のソリューションには以下のような重大な限界がある：

構造化コード vs 非構造化コード: HECOやCHETのようなコンパイラは、構造化された（ループベースの）コードに焦 st する一方、CoyoteやPorcupineなどは、構造化および非構造化（任意の、ループに基づかない）コードの両方を扱うことを試みている。
探索空間の複雑性: 現在の最先端のコンパイラ（例：Coyote、Porcupine）は、ベクトル化を組合せ論的な探索問題としてフレームワーク化している。これらは、手動で調整されたヒューリスティック、整数線形計画法（ILP）、またはプログラム合成に依存して、膨大な設計空間（どの部分式をパッキングするか、データレイアウト、回転挿入の決定など）を探索する。
スケーラビリティと局所最適解: この複雑な空間において、局所的な決定は非局所的な影響（例：パッキングの決定が将来の回転コストを増大させるなど）を及ぼす。単純なヒューリスティックはしばなしばしば悪い局所最適解に陥り、プログラムのサイズが増加するにつれて、網羅的な探索は計算量的に実行不可能になる。

2. 手法

本論文は、ディープ強化学習（RL）を活用してFHEコードの最適化を自動化する新しいフレームワークであるCHEHAB RLを提案している。組合せ論的な探索の代わりに、問題は、書き換えルールの適用シーケンスを学習するポリシーを学習するための、逐次的な意思決定プロセスとして定式化されている。

2.1 フレームワークの概要

CHEHAB RLは、CHEHAB FHEコンパイラに統合されている。ワークフローは以下の通りである：

入力: CHEHABドメイン固有言語（DSL）で記述されたプログラム。これは、抽象構文木（AST）およびデータフローグラフ（DAG）の形式である中間表現（IR）へと低位化される。
RL最適化: RLエージェントがIRを走査し、項書き換えシステム（TRS）から書き換えルールのシーケンスを選択して、スカラーコードのベクトル化、式の簡略化、およびノイズ/レイテンシの最小化を行う。
出力: 最適化されたIRは、Microsoft SEALバックエンド（BFVスキーム）をターゲットとしたC++コードの生成に使用される。

2.2 主要な技術的構成要素

A. 状態表現

RLエージェントのためにプログラムのIRを表現するために、著者らは**識別子および定数不変量（ICI）**トークン化を採用している。

正規化: 変数は名前変更され（例： $v_0, v_1$ ）、0と1を除く定数は汎用的なトークン（ $c_0, c_1$ ）に抽象化される。これにより、命名や特定の定数値に依存しない標準的な形式が作成され、意味的に等価なプログラムを同一の表現へと集約する。
エンコーディング: トークン化されたシーケンスは、Transformerエンコーダ（4層、8つのアテンションヘッド）によって処理され、固定長256次元の埋め込みが生成される。このアーキテクチャは、展開されたFHEプログラムにおける長距離の依存関係をモデル化する能力において、RNN（LSTM/GRU）よりも優れているため採用された。

B. 行動空間

行動空間は、多数のルールと適用場所を扱うように設計されている。

階層的ポリシー: 平坦な行動空間（ルール＋場所）ではなく、エージェントは2段階の階層的ポリシーを使用する：
1. ルール選択ネットワーク: 84個のルールの中から、どの書き換えルールを適用するかを選択するMLP。
2. 場所選択ネットワーク: 第2のMLPが、IR内の特定の場所（マッチインデックス）を選択する。
終了: 特殊なENDアクションにより、エージェントは最適化エピソードを終了できる。

C. 報酬モデル

エージェントは、実行時間とノイズ増加のバランスを取る複合コスト関数を最小化するように訓練される。

コスト関数: $Cost(e) = w_{ops} \cdot C_{ops}(e) + w_{depth} \cdot D_{circuit}(e) + w_{mult} \cdot D_{mult}(e)$ $C os t (e) = w_{o p s} \cdot C_{o p s} (e) + w_{d e pt h} \cdot D_{c i r c u i t} (e) + w_{m u l t} \cdot D_{m u l t} (e)$ 。
- $C_{ops}$ : 操作コストの加重合計（ベクトル加算: 1、ベクトル乗算: 100、回転: 50、スカラー操作: 250）。
- $D_{circuit}$ : 回路の深さ。
- $D_{mult}$ : 乗算の深さ（BFVにおけるノイズ成長に不可欠）。
報酬構造:
- ステップ報酬 ( $R_{step}$ ): 各アクション後のコストの減少率に基づく即時報酬。
- 終端報酬 ( $R_{final}$ ): 初期状態から最終状態までの総コスト減少に基づくグローバルな報酬。これにより、エージェントが局所的に貪欲になることを防ぎ、グローバルに最適な回路を生み出すシーケンスを促進する。

D. 学習データの合成

既存のFHE最適化データセットの欠如を認識し、著者らは大規模言語モデル（LLM、Gemini 2.5 Flash）を使用して、15,855個の一意な式からなる学習データセットを合成した。

LLMによるガイダンス: LLMには、構文規則、書き換えルールの例、および実際のカーネルモチーフ（例：行列加算、二乗差）に関するプロンプトが与えられ、多様で最適化可能なコードパターンを生成させた。
検証: 生成された式は、構文の妥当性、一意性（ICIトークン化による）、およびベンチマークプログラムの除外についてフィルタリングされ、汎用性を確保した。

E. 学習アルゴリズム

エージェントは、単一のマルチコアCPU上で200万タイムステップにわたり、**近接方策最適化（PPO）**アルゴリズムを用いて訓練される。

3. 主要な貢献

定式化: FHEコード最適化を、強化学習によって解決可能な逐次的決定問題として初めて定式化した。
CHEHAB RLフレームワーク: 構造化および非構造化の両方のFHEコードを自動的にベクトル化し、同時にノイズの増加と回路レイテンシを最小化する新しいシステム。これは既存の組合せ論的な探索アプローチよりも優れたスケーラビリティを持つ。
LLM合成データセット: LLMによって生成された大規模で多様な学習データセットの作成と検証。これにより、ランダムなプログラムで訓練する場合よりも大幅に優れたエージェントが得られることが示された。
性能向上: CHEHAB RLが、Coyoteコンパイラと比較して、実行速度で5.3倍、ノイズ蓄積で2.54倍少なく、コンパイル時間で27.9倍高速なコードを生成するという実証的な証拠。
オープンソース: コミュニティへのCHEHAB RLフレームワークの公開。

4. 結果と評価

著者らは、画像処理フィルタ、線形代数カーネル、およびランダムに生成された不規則な多項式を含むベンチマーク・スイートを用いて、Coyote（最先端のベクトル化FHEコンパイラ）と比較評価を行った。

実行時間: CHEHAB RLが生成したコードは、平均してCoyoteよりも5.3倍高速であった。特定のケース（例：線形回帰32）では、速度向上は114倍に達した。これは、RLエージェントが見出したより少ない操作数とより単純なデータレイアウトによるものである。
ノイズ予算: 生成された回路は、平均して2.54倍少ないノイズ予算を消費した。Coyoteがノイズ予算を使い果たして実行に失敗したベンチマークにおいても、CHEHAB RLは有効で実行可能な回路を正常に生成した。
コンパイル時間: RLベースのコンパイルプロセスは、Coyoteの探索ベースのアプローチよりも27.9倍高速であった。RLエージェントは、小さなベンチマークにおいてオーバーヘッド（ニューラルネットワークの推論ステップによる）を伴うものの、Coyoteの組合せ論的な探索が極めて遅くなる大規模な回路において、優れたスケーラビリティを示した。
アブレーション研究:
- LLM vs ランダムデータ: LLM生成データで訓練されたエージェントは、ランダムデータで訓練されたものと比較して、特定のベンチマークで13倍高速な回路を生成した。これは、現実的なコードパターンを学習することの重要性を強調している。
- 報酬設計: ステップ報酬と終端報酬を組み合わせることは、ステップ報酬のみの場合よりも優れた結果をもたらし、局所最適解を防いだ。
- アーキテクチャ: Transformerエンコーダは、プログラム表現の学習においてGRUベースラインを上回り、階層的アクション空間は、学習速度と報酬において平坦なアクション空間を上回った。

5. 意義と主張

本論文は、CHEHAB RLがFHEコンパイルにおけるパラダイムシフトを象徴すると主張している。ヒューリスティック主導の組合せ論的な探索から、学習ベースのポリシー最適化へと移行することで、本フレームワークは従来の設計におけるスケーラビリティと局所最適解の問題に対処している。

著者らは、これがFHE最適化にRLを用いた初めての事例であり、ベクトル化、暗号学的ノイズの蓄積、および操作コストの間のトレードオフを巧みに制御できることを強調している。本研究は、RLエージェントが、手動で調整されたヒューリスティックやILPソルバーを凌駕する、効果的なグローバル戦略（特に非構造化コードに対して）を学習できることを示している。LLMを用いたデータ合成の統合は、そのようなデータが不足している領域において、高品質な学習データを生成するための道筋をさらに明確にしている。

結論として、CHEHAB RLは、基礎となる暗号スキームのセキュリティ保証を維持しながら、暗号化された計算の実行時間とコンパイル時間の両方を大幅に削減することで、FHEの実用的な採用を可能にするものである。