Utilizing Circulant Structure to Optimize the Implementations of Linear Layers

本論文は、対称暗号における線形層の巡回構造を活用して変換系列を構築する新たな手法を提案し、これによりWhirlwindやAESなどのブロック暗号において、従来の最先端の結果と比較して、ヒューリスティックアルゴリズムがXOR回数の大幅な削減と回路深さの効率化を達成することを可能にする。

要約

あなたが特定のレゴブロックのセットを使って複雑な機械を建設しようとする熟練した建築家だと想像してください。暗号学（秘密のコードの科学）の世界では、これらの「機械」は線形層と呼ばれ、データをかき混ぜて安全に保つための働き馬です。

長年、建築家たちは、これらの機械を建設する際に、スペースを節約するために可能な限り少ないブロックを、また速度を節約するために可能な限り短い時間で建設しようと試みてきました。あなたが提供した論文は、設計図に隠されたパターンに気づくことで、これらの機械を設計する新しい方法を紹介しています。

以下に、彼らの発見を簡単に解説します。

1. 問題：複雑さの「壁」

暗号の線形層を、巨大なスイッチの壁だと考えてください。メッセージをかき混ぜるには、これらのスイッチを非常に特定の順序で切り替える必要があります。

• 目標: スイッチを切り替える際の移動回数を最小限に抑え（エネルギー/スペースを節約）、ステップ数を最小限に抑える（高速化する）ことです。
• 従来の方法: 以前の手法は、この壁を巨大で混沌としたスイッチの塊として扱っていました。最適な順序を見つけるために試行錯誤アルゴリズムを使用しましたが、壁があまりにも大きくて散らかっていたため、最も効率的な経路を見逃すことがよくありました。まるで壁にぶつかりながらランダムに迷路を解こうとするようなものです。

2. 発見：「回転する車輪」のパターン

著者たちは、これらの暗号の壁の多くが実際にはランダムではないことに気づきました。これらは巡回構造を持っています。

• 比喩: 回転木馬を想像してください。馬の写真を撮り、その写真を回転させると、馬のパターンはほとんど同じに見えますが、少しずれているだけです。
• 数学的な用語で言えば、行列（スイッチの設計図）は、単一の行を繰り返しシフトさせることで構築されます。これは反復的で回転するパターンです。
• 洞察: 以前の建築家たちは、この「回転木馬」のパターンを無視し、壁を混沌とした塊として扱っていました。著者たちは、このパターンを認識すれば、壁をはるかに効率的に解体できることに気づきました。

3. 解決策：「折りたたみ」のトリック

巨大な壁全体を一度に解こうとするのではなく、著者たちは問題を折りたたむ方法を開発しました。

• 比喩: 反復するパターンを持つ巨大で重いキルトを持っていると想像してください。全体を一度に折りたたもうとするのではなく、パターンが反復しているため、左半分を右半分の上に折り、次に上を下に折ることができることに気づきます。
• この「折りたたみ」技術（行列を数学的に変換する）を使用することで、巨大で複雑な壁を、はるかに単純な三角形の形状に変えることができます。
• 壁がこの三角形の形状に単純化されると、標準的なツールが簡単に仕上げることができます。これは、複雑に絡まった毛糸の玉を、結び目を結ぶ前に整然とした直線に変えるようなものです。

4. 結果：より高速で小型な機械

著者たちは、この新しい「折りたたみ」手法を、一般的なセキュリティシステムで使用されている実際の暗号機械でテストしました。結果は印象的でした。

• 「旋風」機械:

  • 速度: 機械を実行する時間を**39%**削減しました。以前は 1 マイル走るのに 28 秒かかっていた車が、今では 17 秒で走ると想像してください。
  • サイズ: 必要な「ブロック」（論理ゲート）の数を約 30% 削減しました。つまり、機械は小さくなり、消費電力も少なくなります。

• 「AES」機械（ゴールドスタンダード）:

  • AES は世界で最も有名な暗号化標準です。その「MixColumn」部分は、効率的に解くことで有名な難問です。
  • 達成: 著者たちは、数週間かけて手動で設計を微調整する人間の専門家とほぼ同等の結果を達成する自動化システムを構築しました。
  • 注意点: 人間の専門家の設計は 105 個の「ブロック」を使用しました。著者たちの自動化された設計は 107 個を使用しました。手作業ではなく自動化で達成された結果に対して、わずかブロック 2 個分の増加に過ぎません。また、最速の速度（深さ）の記録にも一致しました。

5. なぜこれが重要なのか

• 未来のために: コンピュータ（量子コンピュータを含む）がより強力になるにつれて、これらの「機械」は安全を維持するために、より高速で小型である必要があります。
• 教訓: 設計図に反復的で回転するパターン（回転木馬のような）があることを単に認識することで、著者たちは以前の手法が見逃していたショートカットを見つけました。彼らは新しい種類のブロックを発明したわけではありません。単に、それらを積み上げるより賢い方法を見つけたのです。

要約すると: この論文は、「多くのセキュリティコードは反復パターンに基づいて構築されていることがわかった。そのパターンを使って設計を最初に単純化することで、これまで以上に高速で小型なセキュリティシステムを構築でき、一部の最高の人間の専門家さえも凌駕できる」と述べています。

技術概要

技術的概要：巡回構造の活用による線形層の実装最適化

問題定義
対称暗号における線形層の最適化は、ゲート数や面積に制約される軽量実装と、回路深度や DW コストに制約される量子セキュリティ評価の両方において極めて重要である。一般の可逆行列に対する CNOT 回路（量子）および XOR 回路（古典）の合成にはヒューリスティックアルゴリズムが存在するが、これらは暗号設計に固有の特定の代数構造を十分に活用できていないことが多い。AES の MixColumn や Whirlwind などで広く使用される行列の多くは、巡回構造を有している。Shi と Feng [SF24] による既存の最先端手法などは、これらの行列を一般的な $n \times n$ 二値行列として扱うため、その背後にある巡回特性を活用することで回路深度やゲート数を削減する機会を見逃している可能性がある。

手法
著者は、行列の巡回構造を明示的に活用して効率的な回路の合成を導く新たなフレームワークを提案する。中核となる手法は、$F_{2^k}$ や $GL(F_2, m)$ などの拡大体上の巡回行列を、標準的なヒューリスティック最適化を適用する前に、より単純な形式、具体的には上三角行列に変換する再帰的分解戦略である。

主要な技術的要素は以下の通りである：

1. 再帰的ブロック変換: 定理 3 は、$F_2[x]$ 上の $2^k \times 2^k$ 巡回行列を、基本行・列操作を用いてブロック上三角行列に変換可能であることを示している。アルゴリズムは行列をブロック $A$ と $B$（ここで $M = \begin{smallmatrix} A & B \\ B & A \end{smallmatrix}$）に再帰的に分割し、特定のブロックをゼロにする操作（例：$\begin{smallmatrix} A+B & B \\ A+B & \dots \end{smallmatrix}$ への変換）を適用する。
2. 変換経路の探索: 著者は、再帰ステップにおける行・列操作の選択の違いが、異なる中間行列を生み出すことを観察している。アルゴリズム（アルゴリズム 1）は、より効率的な後続回路をもたらす経路を見つけるために、複数の変換経路（小さな $k$ の場合、最大 $4^{2^k-1}$ の可能性）を探索する。
3. 早期停止とフォールバック: 再帰の恩恵が深さが増すにつれて減少することを認識し、著者は早期に再帰を停止する戦略（アルゴリズム 2）を導入する。アルゴリズムは異なる「ブロックサイズ」を反復して、実質的に再帰深度を変化させる。再帰が早期に停止された場合、生成された行列は、一般的な CNOT/XOR 合成のための標準的なヒューリスティック最適化器（Heu）に渡される。これには、再帰深度をゼロとし、実質的に行列を一般の場合として扱う「フォールバック」戦略も含まれる。
4. 自動最適化: AES に対する Zhang ら [ZSWS24] のような従来の手動アプローチとは異なり、この手法は「より単純な」行列形式と対応するゲート系列を見つけるプロセスを自動化し、人間の介入を不要にする。

主要な貢献

• 新規フレームワーク: 線形層の巡回構造を体系的に活用して回路実装を最適化する最初の研究であり、代数行列の性質と回路合成ヒューリスティックの間のギャップを埋める。
• 自動合成: 手動で行われていたケース固有の最適化を置き換える自動アルゴリズムを提供する。これは、下流のヒューリスティックがより効率的な実装を見つけることを可能にする変換行列の系列を生成する。
• 二重最適化: このフレームワークは、量子回路（CNOT 数と深度の最小化）と古典回路（XOR 数、特に g-XOR および s-XOR の最小化）の両方に適用可能である。

結果
著者は、ブロック暗号（AES、Whirlwind、Clefia、PRIDE など）からの線形層のデータセットと、MDS 行列を構築したデータセット上で手法を評価した。

• 量子回路深度:

  • Whirlwind M0: 提案手法は、回路深度を [SF24] による以前の最先端手法の 28 から 17 に削減し、39% の改善を達成した。ゲート数も 286 から 200 に削減された。
  • AES MixColumn: 自動手法は深度 10 を達成し、Zhang ら [ZSWS24] による手動最適化された最先端結果と一致した。ゲート数は 107 で、手動結果（105）より CNOT が 2 つ多いのみであり、[SF24] が達成した 131 CNOT よりも著しく優れている。
  • その他の行列: 高密度の行列（Whirlwind、SKOP15 8x8 など）では顕著な深度削減が観測されたが、ヒューリスティックが既に良好に機能する疎行列では改善は限定的、あるいは存在しなかった。

• 古典回路（XOR 数）:

  • Whirlwind M0: この手法は s-XOR 数 159 を達成し、Yuan ら [YWS+24] の以前の最良値 173 を約 8% 上回った。
  • 全体的な性能: 多くの行列においてサイズオーバヘッドが発生する傾向があるものの、Whirlwind M0 や M1 などの特定の高密度行列については、最先端の結果を打ち破ることに成功した。

意義と主張
本論文は、巡回構造の活用が線形層を最適化するための、以前は十分に活用されていなかった強力な手段であると主張している。著者は、自らのアプローチが以下の点で優れていると述べている：

1. 標準的な貪欲戦略が困難に直面する特定の高密度行列において、既存のヒューリスティックを凌駕する。
2. 手動最適化を自動化し、AES MixColumn で見られたような、人間の専門家による調整回路と同等の結果を、手動介入なしで達成する。
3. 量子セキュリティ評価における新たな基準を提供し、線形層のより正確な深度推定を可能にする。これは、ポスト量子セキュリティ評価における DW（Depth $\times$ Width）コストの計算に不可欠である。

著者は、この手法がすべての行列タイプ（特に疎な行列）に対して普遍的に優れているわけではないと結論づけているが、巡回構造と高密度を有する行列に対しては大きな利点を提供し、代数特性を回路合成に統合する可能性を実証している。