Constant-time decoding of Gabidulin codes and their generalizations with application to RQC

タイトル： Gabidulin符号およびその一般化の定数時間デコーディング：RQCへの応用

著者： Nicolas Aragon, Chloé Baïsse, Anthony Fraga, Philippe Gaborit, および Ilaria Zappatore (XLIM, CNRS UMR 7252, Université de Limoges)

1. 問題提起

Gabidulin符号は、リード・ソロモン符号のランク計量における類似物であり、RQC（Rank Quasi-Cyclic）やLoidreau暗号システムを含む、いくつかの効率的なランクベース暗号システムの基礎となっています。その暗号学的な有用性にもかかわらず、実用的な展開における重大なギャップが存在していました。すなわち、Gabidulin符号のデコーディングにおける**定数時間実装（constant-time implementation）**が存在しなかったことです。

ポスト量子暗号の文脈、特にNISTの標準化プロセスに続く流れにおいて、定数時間での実行は、タイミング・サイドチャネル攻撃を防ぐための必須要件です。従来のRQCの実装は「ほぼ」定数時間でした。具体的には、Gabidulin符号のデコーディングが、Loidreauのアルゴリズムにおけるユークリッド除法のステップのような、可変時間の操作に依存していたためです。さらに、近年のRQCの改良では、より小さなパラメータサイズを実現するために、拡張Gabidulin（AG）符号（ゼロ列を追加したGabidulin符号）とブロック誤差を利用しています。しかし、これらの特定のAG符号に対する定数時間デコーディングアルゴリズムは存在しておらず、これら暗号システムの安全な実世界での開発を妨げていました。

2. 手法

著者らは、AG符号の定数時間デコーディングを実現するために、アルゴリズムの削減と低レベルの実装最適化を含む包括的な解決策を提案しています。

アルゴリズムの削減（Algorithmic Reduction）：
核心となる理論的貢献は、AG符号のデコーディング問題を標準的なGabidulinデコーディング問題へと削減することです。

• サポート消去の回復（Support Erasure Recovery）： AG符号は、標準的なGabidulin符号にゼロ列を付加することで構成されます。著者らは、受信ベクトルにおいて、最後の $n-n'$ 個の成分がゼロパディングされた位置における誤差に対応しているという構造を利用します。この「サポート消去」（これらの誤差成分によって生成される部分空間）を回復することで、AGデコーディング問題を、より短い長さ（$n'$）、増加した次元（$k+\varepsilon$）、および減少した誤差ランク（$t-\varepsilon$）を持つ標準的なGabidulinデコーディング問題へと変換することができます。
• 複雑度の削減： この削減により、再構成ステップにLoidreauのアルゴリズムを使用することが可能になります。AG符号に対する従来のアプローチは、巨大な線形システムの解法（指数関数的または高多項式的な複雑さ）に依存していましたが、この手法は二次複雑度（$O((n-n')^2)$）を達成します。

定数時間実装：
実装をタイミング攻撃に対して耐性を持たせるため、著者らは$q$-多項式演算に焦点を当てて**RBC（Rank-Based Cryptography）**ライブラリを修正しました。

• 固定反復回数（Fixed Iteration Bounds）： 以前は（秘密である）$q$-多項式の実際の次数に依存していた操作を、固定された上限（$max\_degree$）に依存するように変更しました。
• 定数時間左除算（Constant-Time Left Division）： 作業の大部分は、$q$-多項式の左ユークリッド除法の定数時間版を作成することでした。標準的なアルゴリズムの反復回数は、余りの次数によって変化します。著者らは、実際の更新が不要な場合に「ダミー」操作を実行することで、常に一定のステップ数（$max\_A + 1$）を実行するループを実装しました。
• 最適化： 定数時間実行を維持しながら効率性を確保するため、以下を含むいくつかの最適化を導入しました。
  • $q$-次数と先頭係数の同時計算。
  • 反復フロベニウス自己同型の定数時間逆写像。
  • モノミアルによる$q$-多項式の乗算のための専用関数。
  • 不要な代入を避けるための商の直接的な係数更新。

3. 主な貢献

1. 初の定数時間AGデコーディング： 本論文は、現代的なRQC変種の重要な構成要素である、拡張Gabidulin符号に対する初の定数時間デコーディングアルゴリズムを提示しています。
2. 二次複雑度の証明： 著者らは、AG符号のデコーディングが、Liodreauのアルゴリズムを通じて解ける標準的なGabidulin再構成問題に削減されることにより、二次複雑度で達成できることを証明しました。これは、線形代数的なアプローチによる高次複雑度を回避するものです。
3. 定数時間$q$-多項式演算： 本論文は、$q$-多項式の定数時間操作、特にランク計量デコーディングのボトルネックとなる左除法の完全な記述と実装を提供しています。
4. 統合とベンチマーク： これらのアルゴリズムはRQC-Block-MS-AGスキームに統合されています。実装はタイミング攻撃に対して検証され、他のポスト量子候補と比較されています。

4. 結果

著者らは、Intel Core i7-13700 CPU上で実装の評価を行いました。

• オリジナルRQCとの性能比較： 新しい定数時間実装のRQC-Block-MS-AGは、すべての操作（KeyGen、Encapsulation、Decapsulation）において、元のRQC実装（NISTプロポーザルによるもの）を上回る性能を示しました。
• HQCとの性能比較： ハミング計量に基づくKEMであり、NISTによって選定されたHQCと比較した場合、RQC-Block-MS-AGの実装はCPUサイクル数において約4〜5倍遅いです。
• サイズのトレードオフ： 性能の差にもかかわらず、RQC-Block-MS-AGスキームは、HQCよりも約4倍小さい公開鍵および暗号文サイズを実現しています。
• 拡張Gabidulin（EG）符号との比較： 著者らは、AG符号のデコーディング手法を拡張Gabidulin（EG）符号のデコーディングと比較しました。結果は、AGデコーディングが、同等のパラメータにおいてEGデコーディングよりも大幅に高速であること（乗算とフロベニウス操作が約3倍少なく、CPUサイクルが約2倍少ない）を示しており、AG符号の特定の構造が復号においてより効率的であることを裏付けています。
• 定数時間検証：
  • タイミング分析： 平均デコーディング時間は、異なる誤差重み（0から36）にわたって0.2%未満の差しかなく、従来のアルゴリズムに見られた誤差重みと実行時間の相関を排除しています。
  • Valgrind分析： データポイズニングを用いたValgrindのmemcheckツールを使用し、実装内に秘密依存の分岐やメモリアクセスが残っていないことを検証しました。

5. 意義と主張

本論文は、ランク計量暗号における決定的なセキュリティ上のボトルネックを解決することを主張しています。AG符号に対する初の定数時間デコーディングを提供することで、著者らはRQC暗号システムとその変種の安全な実世界での展開を可能にします。

この研究の意義は、それが提示するトレードオフにあります。実装は主要なハミング計量候補（HQC）よりも遅いものの、4倍の削減された鍵および暗号文サイズを提供します。著者らは、これは帯域幅やストレージが制約となる環境において「魅力的なトレードオフ」であると主張しています。

さらに、本論文は、AG符号のために開発された技術（特に定数時間左除法と削減戦略）が、標準的なGabidulin符号のデコーディングを最適化するためにも直接適用可能であることを強調しています。AGデコーディングはGabidulinのケースを一般化したものであるためです。著者らは、今後の課題として、コンパクトなパラメータを維持しながら性能をさらに向上させるために、高次元Gabidulin符号のシンドロームデコーディングを探索できる可能性を示唆しています。