Quantum Key Search Algorithms under Side-channel Attack

技術要約：サイドチャネル攻撃下における量子鍵探索アルゴリズム

問題提起
本研究は、サイドチャネル攻撃（SCA）から得られたノイズを含む鍵を攻撃者が保有している場合の、暗号アルゴリズムにおける鍵探索問題に対処するものである。このシナリオでは、攻撃者は真のターゲット鍵 $k^*$ とは一定数のビット反転（ハミング距離）で異なる鍵 $Y$ を入手する。鍵空間の確率分布は一様ではなく、ビット誤り率（BER）$\alpha$ によって決定される $n$ 重ベルヌーイ分布に従う。課題は、この非一様な鍵空間を効率的に探索して $k^*$ を見つけ出すことであり、その際、ノイズを含む鍵から提供される事前情報を活用する必要がある。古典的な総当たり探索は $O(N)$ 回のクエリを必要とし、標準的なグローバーのアルゴリズムは $O(\sqrt{N})$ 回のクエリを必要とするが、いずれもサイドチャネル攻撃によって誘発されるベルヌーイ分布の特定の構造を十分に活用できていない。さらに、モンタナロ（Montanaro）のアルゴリズムのような既存の量子アプローチは、等しい事後確率を持つ鍵のブロックに対して必要な特定の初期重ね合わせ状態を準備することにおいて困難に直面している。

手法
著者らは、理論的モデリング、アルゴリズム設計、および状態準備にわたる包括的なフレームワークを提案している。

1. 確率的モデリング: 本研究では、独立同一分布（i.i.d.）のビット反転確率 $\alpha$ を仮定して鍵空間の分布をモデル化している。ベイズの定理を用いることで、候補鍵の事後確率は、ノイズを含む鍵 $Y$ からのハミング距離 $d$ のみに依存することが示される。これにより、同じハミング距離を持つ鍵はすべて同じ事後確率を共有することが確立される。
2. 古典的ベースライン: 候補鍵を事後確率の降順（すなわち、ハミング距離 $d=0$ から $d=n$ まで）で辿る古典的な鍵探索アルゴリズムを導出する。期待クエリ計算量 $G_c$ は、各距離における候補鍵の二項分布に基づいて厳密に算出される。
3. 改良された量子アルゴリズム:
   • 分割戦略: 幾何級数的に増大するブロック $\{1, c, c^2, \dots\}$ に鍵空間を分割するモンタナロのアルゴリズムとは異なり、本論文では、ハミング距離 $d$ に基づいて鍵空間を $(n+1)$ 個のブロック $\{R_0, R_1, \dots, R_n\}$ に分割することを提案する。各ブロック $R_d$ は、正確に $d$ 個のビットエラーを持つ $\binom{n}{d}$ 個の候補鍵を含む。
   • 探索の実行: アルゴリズムは、確率の減少（距離 $d$ の増加）に従ってこれらのブロックを反復処理する。各ブロック $R_d$ に対して、そのブロック内の鍵の一様重ね合わせ状態を準備し、グローバーの探索を適用する。
   • 計算量分析: 量子クエリ計算量 $G_q$ は、ターゲット鍵がそのブロックに存在する確率で重み付けされた、各ブロックにおけるグローバー探索のコストを合算することによって導出される。
4. 初期状態の準備: 各ブロック $R_d$ の特定の重ね合わせ状態を準備することの困難に対処するため、著者らは候補鍵の状態とディッケ状態（Dicke state） $|D^n_d\rangle$ との間の等価性を確立している。彼らは、ノイズを含む鍵 $Y$ のハミング距離 $d$ にある鍵の一様重ね合わせ状態は、ディッケ状態 $|D^n_d\rangle$ にパウリ $X$ 演算子のテンソル積 ($X^{\otimes Y}$) を適用することで生成できることを証明している。
   • 実装: ディッケ状態は、補助量子ビットを必要としない、Bärtschi と Eidenbenz の研究に基づく短深度の分割統治回路を用いて準備される。最終的な状態は、ノイズを含む鍵 $Y$ に基づいて $O(d)$ 個の $X$ ゲートを適用することで得られる。

主な貢献

• 理論的導出: 本論文は、サイドチャネル攻撃条件下における計算量の厳密な導出を提供しており、特に $n$ 重ベルヌーイ分布をモデル化している。
• アルゴリズムの改善: ハミング距離に基づくブロック分割戦略を利用した、改良された量子鍵探索アルゴリズムを導入している。この戦略は、モンタナロのアルゴリズムで使用されている幾何学的分割よりも、SCAシナリオにおける実際の鍵分布と一致していることが示されている。
• 状態準備の解決策: 入力状態準備のボトルネックを、問題をディッケ状態の準備へと変換することで解決している。必要な状態が、$O(d \log \frac{n}{d})$（イオントラップ・トポロジーの場合）または $O(\sqrt{nd})$（超伝導トポロジーの場合）の回路深度と、$O(nd)$ 個の CNOT ゲートを用いて、補助量子ビットなしで生成できることを実証している。

結果
ビット誤り率（BER）が 1% ($\alpha = 0.01$) の 256 ビット暗号鍵に関するシミュレーション結果は、大幅な性能向上を示している。

• 計算量の削減: SCA 条件下の古典的アルゴリズムによるクエリ計算量は、$2^{256}$（SCA なし）から $2^{62.29}$ へと減少する。提案された量子アルゴリズムは、これをさらに $2^{19.77}$ まで削減する。
• 加速因子: 提案された量子アルゴリズムは、SCA 条件下の古典的アルゴリズムに対して 3.15 倍 の加速を実現している。これは、同じ条件下で Glaser らが報告した（モンタナロのアルゴリズムを分析した）加速因子 2.73 倍 と比較される。著者らは、自らの探索効率が [9] で提案されたモンタナロの幾何級数成長アルゴリズムによる効率よりも 15.38% 高いことを指摘している。
• 境界値との比較: 本論文は、導出された量子クエリ計算量 ($2^{19.77}$) が、この特定の分布シナリオにおける Glaser によるモンタナロのアルゴリズムの推定上限/下限 ($2^{21.59}$ および $2^{17.59}$) よりも精密かつタイトであることを主張している。
• リソース効率: 状態準備スキームは短深度回路で実現可能であることが示されており、$n=256, d=4$ の場合の具体的なリソース数（例：1024 個の CNOT ゲート、0 個の補助量子ビット）が提供されている。

意義
本論文は、その研究が、サイドチャネル攻撃下における量子暗号解読のための、理論的分析から実践的な実装に至るフルチェーンのソリューションを提供すると主張している。サイドチャネルノイズの特定の構造（ベルヌーイ分布）を活用することで、提案されたアルゴリズムは古典的な対抗策に対して**超多項式的な加速（super-quadratic speedup）**を実現し、モンタロのような従来の量子探索適応手法を凌駕している。必要な初期状態を短深度かつ補助量子ビットなしの回路を用いて準備できる能力は、実用的な量子鍵探索の展開における重要な障壁を解消する。著者らは、これらの結果が、ノイズを含む鍵という事前情報が利用可能なシナリオにおいて、より正確な計算量の推定と、より効率的な探索戦略を提供するものであると断言している。今後の課題として、このアルゴリズムを特定の暗号（AES, SM4）と統合することや、量子ノイズの影響を分析することが挙げられている。