Quantum Circuit Realization and Grover Cryptanalysis of the Hybrid ARX-SPN Cipher GFSPX

本論文は、軽量ハイブリッド ARX-SPN 暗号 GFSPX の量子ビット最適化量子回路実装を提示し、並列化されたグローバー攻撃を通じてそのポスト量子セキュリティを評価し、NIST レベル 1 の閾値を下回るものの他の軽量設計と比較して優れた耐性を示す総量子コスト$1.12 \times 2^{159}$ゲートであることを明らかにする。

要約

非常に軽量なデジタルロック（GFSPX と呼ばれる）を、スマートセンサーや RFID タグのような小型デバイスのデータ保護のために設計したと想像してください。このロックは高速で極めて少ないエネルギーで動作するように作られており、「モノのインターネット（IoT）」に最適です。

しかし、量子コンピュータと呼ばれる新しい種類の「スーパーツール」が登場しつつあります。通常のコンピュータが鍵を一つずつ確認するのとは異なり、量子コンピュータは一度に多数の鍵を確認でき、これらのロックをより速く解読する可能性があります。この論文は、単純な問いを投げかけます：もし量子コンピュータがこの特定のロックを破ろうとした場合、実際にはどれほど困難なのでしょうか？

以下に、日常の比喩を用いた彼らの発見の概要を示します：

1. ロックの設計：ハイブリッドエンジン

GFSPX ロックは、単一のメカニズムだけで構成されているわけではありません。ガソリンエンジンと電気モーターの両方を使用する自動車のようなハイブリッドです。

• 「ガソリン」部分（ARX）： これは非常に効率的ですが、データ全体に変化を広げるのにやや時間がかかる、単純な数学的演算（加算、回転、排他的論理和）を使用します。
• 「電気」部分（SPN）： これは（カードをシャッフルするような）複雑な置換ネットワークを使用し、変化を非常に素早く広げます。
• 結果： これらを組み合わせることで、ロックは高速かつ効率的になります。著者らは、内部の仕組みを正確に把握するために、量子コンピュータ向けにこのロックのデジタル設計図を作成しました。

2. 量子設計図：回路の構築

ロックをテストするために、研究者たちは「量子回路」を構築する必要がありました。これは、すべてのステップが完全に元に戻せる（したがって情報が失われない）ミニチュアで可逆的な工場を構築するようなものです。

• 課題： 量子コンピュータは脆弱です。データを単にコピーして回すことはできず、「キュービット」（小さな回転するコマのような量子ビット）を非常に慎重に扱わなければなりません。
• 解決策： 研究者たちは設計を最適化し、可能な限り少ないキュービット（209 個）を使用するようにしました。数学的部分には「リップル・キャリー・アダダー」と呼ばれる巧妙なトリックを使用しました。これはスペースを無駄にしない非常に効率的な組立ラインのようなものです。
• ** footprint（足跡）：** 最終的な設計図はコンパクトで、1 回の完全な暗号化を実行するには「工場フロア」として 209 個のキュービットと、特定のステップ数（ゲート）が必要です。

3. 攻撃：「グローバー」探索

ロックを破るために、量子コンピュータはグローバーのアルゴリズムを使用します。

• 比喩： $2^{128}$（理解するのが難しいほど巨大な数）冊の本があり、そのうち正しい鍵を持つ本が 1 冊だけある巨大な図書館があると想像してください。
  • 通常のコンピュータは、1 冊ずつ本を確認する司書のようなものです。これには永遠にかかります。
  • 量子コンピュータは、同時に多数の本を確認できる魔法の司書のようなものです。正しい本を見つけるには、おおよそ時間の平方根で済みます。
• 罠： 量子コンピュータが間違った本（「偽陽性」）を選ばないようにするために、研究者たちはコンピュータに同時に3 つの異なるロック（3 つの異なる平文と暗号文のペアを使用）を確認させました。もしある鍵が 3 つすべてを開けるなら、それは間違いなく正しい鍵です。

4. 判決：強力だが「ポスト量子」証明ではない

研究者たちは、この量子攻撃の総「コスト」を計算しました。

• コスト： ロックを破るには、$1.12 \times 2^{159}$ 回の演算に相当する膨大な計算能力が必要であることがわかりました。
• 基準： 米国国立標準技術研究所（NIST）は未来のための「安全基準」を設定しています。量子コンピュータに対して真に安全と見なされるためには（レベル 1 のセキュリティ）、ロックのコストは少なくとも $2^{170}$ である必要があります。
• 結果： GFSPX ロックは安全基準を下回っています。最も厳格なポスト量子基準に対しては安全ではありません。
  • ただし、この論文は、他の軽量ロックと比較すると、GFSPX は実際には破るのに最も難しいものの一つであると指摘しています。これは、小型デバイスにとって非常に効率的でありながら、量子攻撃に対するそれなりの耐性も提供するという「絶妙なバランス点」に位置しています（最高レベルのセキュリティ試験には合格しなくても）。

5. 結論

この論文は、このハイブリッドロックが現在のリソース制約のあるデバイスには優れているものの、128 ビットの鍵サイズは、将来の決意ある量子攻撃を生き延びるには単に小さすぎるという結論を下しています。

• トレードオフ： 小型で高速なロック（今日のセンサー向けに良い）か、巨大で低速なロック（将来の量子安全性向けに良い）のどちらかを選ぶことができますが、この特定の設計は両方を行おうとして「将来の安全性」の面でわずかに不足しています。
• 将来の助言： この設計を真に量子耐性にするために、著者たちは鍵を長くする（192 ビットまたは 256 ビットなど）か、量子コンピュータによる処理をさらに困難にするために数学的部分を調整することを提案しています。

要約すると：GFSPX は非常に巧妙で効率的なロックであり、その同類の多くよりも解読が難しいですが、いくつかのアップグレードなしには将来の超強力な量子コンピュータに耐えるには十分に強固ではありません。

技術概要

技術概要：ハイブリッド ARX-SPN 暗号 GFSPX の量子回路実装とグロバー暗号解析

問題提起
量子コンピューティングの出現は、古典的な対称鍵プリミティブのセキュリティに根本的な挑戦を突きつけている。ショアのアルゴリズムが公開鍵暗号を脅かす一方で、グロアのアルゴリズムは非構造化検索に対して二次的な高速化を提供し、対称鍵構成のセキュリティマージンを事実上半分に減らす。したがって、IoT や RFID などのリソース制約環境向けに設計された軽量ブロック暗号（BC）は、ポスト量子耐性について厳密な再評価を必要とする。具体的には、加算・回転・排他的論理和（ARX）と置換・置換ネットワーク（SPN）のパラダイムを組み合わせたハイブリッド設計に対して鍵回復攻撃を仕掛けるために必要な量子リソースを定量化する必要がある。

手法
著者らは、64 ビットデータブロックと 128 ビット秘密鍵を特徴とする軽量ブロック暗号 GFSPX の包括的な量子回路実装とグロバー暗号解析を提示する。GFSPX は、非線形性のための ARX ベースの関数（$F_1$）と高速拡散のための 32 ビット SPN 構造（$F_2$）を統合する 4 分岐一般化フェistel構造（GFS）を採用している。

手法は 3 つの段階で進行する：

1. 量子回路実装：GFSPX の古典的構造を可逆量子回路にマッピングする。著者らはフェistelネットワークの固有の可逆性を利用して、補助量子ビットの使用を最小化する。
   • $F_1$（ARX）：Cuccaro らのアーキテクチャに基づくコンパクトなリップルキャリー加算器（RCA）を用いて実装される。このアプローチは、モジュラ加算の最終キャリービットを省略し、その場で実行される MAJ（Majority）および UMA（UnMajority-and-Add）ゲートを活用することで、量子ビットのオーバーヘッドを最小化する。
   • $F_2$（SPN）：S ボックス層（PRESENT に基づく）は、追加の補助量子ビットなしで最小限の CNOT ゲートとトフォリゲートのセットを用いて合成される。置換層（P レイヤー）は、回路深度を低く保つために並列化可能な SWAP ゲートを通じて実装される。
   • 鍵スケジューリング：128 ビットマスター鍵スケジューリングは、113 ビット左巡回回転、S ボックス置換、ラウンドカウンタの排他的論理和を含むユニタリ進化として実現され、その場で実行するように最適化されている。
2. リソース推定：量子コストは、標準的な分解メトリクス（NOT および CNOT コスト＝1、トフォリコスト＝6）を用いて計算される。分析では、SWAP ルーティングオーバーヘッドを除外したベースラインコストと、SWAP を 3 つの CNOT に分解した上限の両方を評価する。
3. グロバー暗号解析：鍵回復攻撃に対する暗号の評価を行うために、並列化されたグロバーオラクル（$U_f$）が構築される。128 ビット鍵空間における誤った一致を排除するため、オラクルは 3 つの平文 - 暗号文ペア（$r=3$）を利用する。攻撃の複雑さは、オラクルのリソースメトリクスを最適なグロバー反復回数（$\approx \frac{\pi}{4}2^{64}$）でスケーリングすることで推定される。

主な貢献

• 最適化された量子実装：本論文は、GFSPX 用の量子ビットを最適化した量子回路を提供し、209 量子ビットのフットプリントを達成する。この設計は、7,617の回路深度で32,498ゲートのベースライン量子コストを達成する。
• ハイブリッドアーキテクチャ分析：本研究は、ハイブリッド ARX-SPN 設計のリソース分布を詳細に記述し、モジュラ加算プリミティブが総ゲート数を支配している一方で、SPN コンポーネント内の並列化された置換層が競争力のあるゲート対深度比の維持に寄与していることを実証する。
• 定量的セキュリティ評価：著者らは 3 つの平文 - 暗号文ペアを用いてグロバーオラクルを構築し、NIST の MAXDEPTH フレームワークの下での総攻撃コストを計算する。分析により、$r=3$の場合の総量子攻撃コストは約$1.12 \times 2^{159}$ゲートであることが明らかになった。
• 比較ベンチマーク：実装は、他の軽量暗号（PRESEN、GIFT、SIMON、SPECK など）に対してベンチマークされる。GFSPX は比較対象の設計の中で最も低いコスト対深度比（4.27）を達成し、高い並列実行効率を示している。

結果

• リソースメトリクス：完全な 20 ラウンド GFSPX 回路は 209 量子ビットを必要とする。ベースラインコストは 32,498 であり、SWAP ルーティングオーバーヘッドを含めると 47,789 に上昇する。回路深度は 7,617 である。
• 攻撃の複雑さ：鍵回復攻撃の総量子コストは、$r=3$の場合、$1.12 \times 2^{159}$と推定される。
• セキュリティ分類：NIST ポスト量子暗号フレームワークにおいて、レベル 1 のセキュリティ閾値（AES-128 に相当）は、少なくとも$2^{170}$の総攻撃コストを必要とする。GFSPX の推定コスト（$2^{159}$）はこの閾値を下回る。
• 設計のトレードオフ：GFSPX は、純粋な SPN 設計（$2^{152}$周辺に集まる）よりも高い量子攻撃耐性を示しているが、128 ビット鍵長では NIST レベル 1 のセキュリティ基準を満たしていない。ハイブリッド設計のコストは ARX コンポーネント（モジュラ加算）の影響を強く受けており、そのセキュリティプロファイルは SIMON や SPECK などの ARX ベースの暗号に近い。

重要性
本論文は、その発見が次世代暗号設計における古典的ハードウェア効率と量子耐性のバランスに関する重要な洞察を提供すると主張している。本研究は、根本的なトレードオフを浮き彫りにする。すなわち、ハイブリッド ARX-SPN 構成は、純粋な SPN 設計よりも堅牢な古典的パフォーマンスと優れた量子耐性を提供する一方で、128 ビット鍵長は高度な量子敵対者に対する NIST レベル 1 のセキュリティを達成するには構造的に不十分であるということである。著者らは、将来の研究が鍵長の延長（例：192 ビットまたは 256 ビットへ）や可逆モジュラ加算プリミティブの最適化に焦点を当ててセキュリティマージンを改善すべきであると示唆している。この研究で確立された手法は、リソース制約環境における他のハイブリッド設計を評価するための厳密な枠組みとして機能する。