EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity

技術要約：一方向パズルを伴わないEFIペア

1. 問題提起と動機

量子暗号学においては、古典暗号における一方向関数（OWF）に相当する単一の最小限のプリミティブが現在欠如している。これらに対して、2つの主要な候補が浮上している：

1. EFIペア（効率的な準備可能性、統計的な隔たり、計算量的な不可識別性）：容易に生成可能であり、統計的に区別できるが、計算量的には区別不可能な一対の混合量子状態。EFIペアは量子ビットコミットメントと等価であり、安全なマルチパーティ計算を可能にする。
2. 一方向パズル（OWPuzzs）：サンプラーが古典的なパズル $s$ と鍵 $k$ を生成し、無制限の検証者が鍵を検証する組 $(Samp, Ver)$。OWPuzzsはEFIペアを内包するが、その逆が成立するかどうかは未解決の問いである。

中心的な未解決問題は、EFIペアに必要な困難さ（量子状態の不可識別性）が、OWPuzzsに必要な古典的な平均ケースの困難さ（探索問題の逆転）を必ずしも意味するかどうかである。具体的には、EFIペアは存在するが、OWPuzzs（たとえ非効率な検証者であっても）は存在しないようなオラクルが存在するかどうかである。

2. 手法とオラクル構成

著者は、これらのプリミティブを分離する単一の決定論的な古典オラクル $\mathcal{O}'$ を構築している。このオラクルは2つのレイヤーで構成される：

1. 状態ソース ($R$)：入力 $(b, 1^\lambda)$ に対して、新鮮な混合状態 $\rho_{b,\lambda}$ を返す。これらの状態は、ハール乱数に従う半次元部分空間 $H \subseteq \mathbb{R}^n$ （ここで $n=2^\lambda$）から構築される。具体的には、$\rho_0$ は $H$ 上の最大混合状態であり、$\rho_1$ は $H^\perp$ 上の最大混合状態である。
2. **カウント・オラクル ($Count$)**：古典的出力を持つオラクル補助付き量子サンプラー$C$の記述を与えられると、出力確率$\Pr[C^{\mathcal{O}}(1^\lambda) = x]$の正確なビットを返す。循環参照を避けるため、クエリは**ランク**によって階層化される：ランク$r$のクエリは、自身のオラクル呼び出しのランクが厳密に$r$ 未満であるサンプラーについてのみ質問できる。

アクセスモデル（Coherent-Last / 最後のコヒーレントアクセス）：EFIペアの安全性は、coherent-last access を持つ識別者に対して証明される。このモデルは以下を許容する：

• 多項式長の古典的助言（または $O(\lambda)$ 量子ビットの量子助言）。
• オラクルへの多項回数の適応的な古典的クエリ。
• 相互作用の最後にちょうど一度だけ行われるコヒーレント（重ね合わせ）クエリ。
• （公開ソースによって生成された）チャレンジ状態の参照コピーの多項回数の利用。

3. 主な貢献と結果

A. 一方向パズルの非存在（定理 A(i)）
$\mathcal{O}'$ の相対において、OWPuzzsは存在しない。これは、検証者が計算量的に無制限である場合でも同様である。

• メカニズム：$Count$ オラクルにより、アドバーサリは多項回の古典的クエリを用いて、任意のサンプラーの出力確率を指数精度の精度で推定できる。
• 攻撃：アドバーサリは、ビットごとに条件付き分布を再構成できる。これらの推定された条件付き確率からサンプリングすることで、アドバーサリは確率 $1 - \text{negl}(\lambda)$ で検証者に受理される鍵を生成できる。
• 範囲：この攻撃は純粋に古典的であり、アドバーサリがオラクルへの完全なコヒーレントアクセス（全コヒーレントアクセス）を持っている場合でも適用される（なぜなら、攻撃は量子クエリに依存しないためである）。したがって、OWPuzzsによって示唆されるすべてのプリミティブ（マルチコピー擬似ランダム状態、純出力一方向状態生成器、量子マネーなど）も、$\mathcal{O}'$ の相対においては存在しない。

B. EFIペアの存在（定理 A(ii)）
$\mathcal{O}'$ の相対において、半部分空間ペア $(\rho_0, \rho_1)$ は、定義されたアクセスモデルに対して安全なEFIペアを形成する。

• 古典的クエリ（通信複雑性の低減）：古典的クエリに対する安全性は、ベクトル・イン・サブスペース (VSP) 問題への帰着に還元される。VSPでは、ボブは部分空間 $H$ を保持し、アリスは $H$ または $H^\perp$ に含まれることが約束されたベクトルを保持する。
  • 量子の場合：VSPは容易である（アリスは $O(\log n)$ 量子ビットでベクトルを送り、ボブは測定する）。
  • 古典的な場合：VSPは困難であり、$\Omega(n^{1/3})$ ビットの通信を必要とする（Klartag–Regevの境界）。
  • 著者は、$H$ に関する長さ $L$ のいかなる古典的トランスクリプトも、状態を識別する上で高々 $O(L/n^{1/3})$ のアドバンテージしか提供しないことを示している。アドバーサリは多項式の長さの古典的ビットしか持たないため、アドバンテージは無視できる（negligible）となる。
• 参照コピー：アドバーサリには状態の参照コピーが与えられる。著者は、これらをコピーの生成（span）の古典的記述で置き換えられることを示す。これらの生成に条件付けることで、問題は直交補空間におけるより小さなVSPインスタンスへと還元され、安全性への損失は極めて僅かである。
• コヒーレント・クエリ：相互作用の最後に許可される単一のコヒーレント・クエリは、ランダム行列論のツールを用いて制限される。1クエリのアドバーサリのバイアスは $O(\sqrt{\log M / n})$ であることが示されており、これは多項式幅 $M$ に対して無視できる。注記：EFIの安全性に関する主張は、この「coherent-last」モデルに限定されている。

C. インタラクティブな崩壊（定理 B）
$\mathcal{O}'$ の相対において、古典的なメッセージを伴うプロトコルの量子性を証明することはできない。そのようなプロトコルにおける任意の量子多項式時間（QP）の当事者は、$\mathcal{O}'$ に対する古典的クエリを行う古典的多項式時間（P）の当事者によってシミュレート可能である。これは、このオラクル世界において、古典的な入力と出力を持つあらゆるタスクに対して、量子多項式時間が古典的多項式時間に対して優位性を持たないことを意味する。

D. プリミティブの分離
本論文は、モデル1.1で定義された識別器のクラス内において、EFIペアからOWPuzzsを構築する完全なブラックボックス構成は存在しないというブラックボックス・バリアを確立している。これにより、「NanoCrypt」の世界（EFIペアは存在するが、OWPuzzsは存在しない）と「CountCrypt」の世界（OWPuzzsが存在する）を分離している。

4. 意義と限界

意義:

• 困難性の分離：本研究は、量子状態を区別する困難さ（EFI）が、必ずしも古典的な探索問題（OWPuzzs）の困難さを意味しないことを示している。これは、量子暗号の最小限の仮定が、古典的な平均ケースの困難さよりも弱い可能性があることを示唆している。
• 新しい証明手法：本論文は、量子状態の不可識別性を古典的な通信複雑性の下界（特にVSP）に還元するという新しい手法を導入している。
• オラクル構成：古典的な出力の困難さ（探索、決定、および相互作用）を取り除きつつ、量子状態の不可識別性（coherent-lastの制限下）を維持する、具体的な単一の古典オラクルを提供している。

限界と未解決の問い:

• コヒーレントアクセス：EFIの安全性証明は、最後の一回のコヒーレント・クエリという制限に基づいている。本論文は、アドバーサリが古典的オラクルに対して完全なコヒーレントアクセス（複数の適応的な重ね合わせクエリ）を持つ場合にも、この分離が成立するかどうかという問い（予想8.2）を残している。
• 助言（Advice）：安全性は $O(\lambda)$ 量子ビットの量子助言に対して保持されるが、多項式サイズの量子助言と古典的クエリの組み合わせ（これにより、アドバーサリは古典的トランスクリプトの前に任意の量子サイド情報を合成できる可能性がある）については排除していない。
• 相対化：これらの結果はオラクルによる分離である。これらは、非相対的な世界においてEFIペアからOWPuzzsが構築可能かどうかを解決するものではなく、また $P \neq PSPACE$ を示唆するものでもない。

要約すると、本論文は、古典的な平均ケースの困難さ（OWPuzzsに必要とされるもの）に依存することなく、量子状態の不可識別性（EFIペア）に依拠した量子暗号が可能となるオラクル世界を構築しており、これにより量子暗号における最小限の仮定の景観を明確にしている。