Quantum Oracle Distribution Switching and its Applications to Fully Anonymous Ring Signatures

1. 問題提起 (Problem)

• 背景: リング署名は、グループのメンバーが自身の正体を明かさずにグループを代表してメッセージに署名することを可能にする暗号プリミティブです。これは、Signal プロトコルなどのエンドツーエンド暗号化メッセージングサービスにおける「否認可能な認証鍵交換（DAKE）」の実装に不可欠です。
• 現状の課題: 既存のポスト量子リング署名構成（AOS 変換を用いたものや、リングトラップドアに基づく Gandalf や FalconRS などの構成）は、古典的なランダムオラクルモデル（ROM）では安全であることが証明されています。しかし、量子計算機に対する安全性（QROM での安全性）は証明されていません。
• 技術的障壁:
  • 従来の ROM 証明で用いられていた「履歴フリー（history-free）」な証明手法や、レニー分散（Rényi divergence）を用いた解析手法は、量子オラクルへのアクセスを考慮するとそのまま適用できない、あるいは破綻する可能性があります。
  • 特に、レニー分散を用いてオラクルの分布を置き換える際、量子アルゴリズム（Deutsch-Jozsa アルゴリズムなど）が古典的な場合とは異なる振る舞いをするため、単純な乗法的な境界（multiplicative bound）が成立しないことが知られていました。

2. 手法と技術的基盤 (Methodology)

著者らは、QROM における安全性証明を確立するために、以下の新しい技術的ツールとアプローチを開発・適用しました。

A. 量子オラクル分布スイッチング (Quantum Oracle Distribution Switching)

オラクルの出力分布が 2 つの異なる確率分布 $P$ と $Q$ のいずれかから独立にサンプリングされる場合の、量子アルゴリズムの識別能力を分析しました。

• 統計的距離 (Statistical Distance) による境界: 圧縮オラクル（Compressed Oracle）の手法を用いて、$q$ 回の量子クエリに対する出力分布の統計的距離が $O(q\sqrt{\epsilon})$ （$\epsilon$ は $P$ と $Q$ の統計的距離）で抑えられることを示しました。これは既存の結果を改善し、明示的な定数を含みます。
• レニー分散の限界と解決策:
  • 限界: 分布 $P$ と $Q$ の全体を置き換える場合、レニー分散を用いた乗法的な境界は量子設定では成立しないことを示しました（Deutsch-Jozsa アルゴリズムを用いた反例の構築）。
  • 解決策（適応的再プログラミング）: 全体を置き換えるのではなく、署名オラクルで使われる特定の位置（入力）のみを再プログラミング（リサンプリング）する場合、レニー分散の古典的な性質を部分的に適用できることを示しました。これにより、塩（salt）を追加した構成において、レニー分散を用いた tight な安全性証明が可能になります。

B. 2 種類のリング署名構成への適用

論文では、Signal 準拠の DAKE に使用される 2 種類の主要なリング署名構成に対して、QROM での安全性証明を提供します。

1. リングトラップドア関数 (RPSF) に基づく構成:

   • Gandalf や FalconRS などの構成を一般化し、「リング事前サンプル可能関数（Ring Preimage Sampleable Functions: RPSF）」という新しいプリミティブを定義しました。
   • 証明手法 1（履歴フリー）: 統計的距離と圧縮オラクルを用いた履歴フリーな還元（history-free reduction）により、QROM での安全性を示しました。
   • 証明手法 2（レニー分散）: 上記の「分布スイッチング」の知見を活用し、レニー分散に基づく証明を提供しました。これにより、より tight なパラメータ設定が可能になります。

2. AOS 変換（Abe-Ohkubo-Suzuki）に基づく構成:

   • $\Sigma$-プロトコルをリング署名に変換する AOS 変換の QROM 安全性を初めて証明しました。
   • 一般 $\Sigma$-プロトコル: 「測定と再プログラミング（Measure-and-Reprogram）」手法を用いて、UF-NRA（No-Ring Attack 下での不可偽性）への還元を行いました。ただし、リングサイズ $N$ に対して指数関数的な損失が生じます。
   • Commit-and-Open (C&O) $\Sigma$-プロトコル: 直線的な抽出（straightline extraction）技術と圧縮オラクルのデータベース特性を用いて、乗法的に tight な還元を提供しました。Merkle 木ベースの構成にも拡張可能です。

3. 主要な貢献 (Key Contributions)

1. QROM における 4 つの安全性還元:

   • AOS 構成に対して 2 つ（一般 $\Sigma$-プロトコル用と C&O 用）。
   • RPSF 構成に対して 2 つ（統計的距離ベースとレニー分散ベース）。
     これにより、Signal 準拠の DAKE に使用される主要なリング署名構成のポスト量子安全性が初めて QROM で保証されました。

2. 量子オラクル分布スイッチングの理論的進展:

   • 量子アルゴリズムが異なる分布を持つオラクルと相互作用する際の統計的距離の tight な境界を導出しました。
   • レニー分散が量子設定で全体分布の置き換えに使用できないことを示し、その代わりに「部分的な再プログラミング」を通じてレニー分散を有効活用する手法を確立しました。

3. Falcon 署名への示唆:

   • 同様の技術的課題が NIST 候補である Falcon 署名の QROM 証明にも存在することを指摘し、本研究で開発された手法（特にレニー分散と適応的再プログラミングの組み合わせ）が Falcon の完全な QROM 解析の鍵となり得ると示唆しました。

4. 結果 (Results)

• 安全性の保証: 既存の ROM 証明のみを持っていたリング署名構成（Erebor, MayoRS, Gandalf, FalconRS など）が、QROM においても安全であることを示しました。
• パラメータの tightness:
  • AOS 構成において、C&O $\Sigma$-プロトコルを用いることで、リングサイズ $N$ に対する指数関数的な損失を回避し、乗法的に tight な証明が可能であることを示しました。
  • RPSF 構成において、塩（salt）の導入により、レニー分散の性質を活用した tight な安全性評価が可能になりました。
• 実用性: 結果として得られるセキュリティ損失は、古典的な証明から QROM へ移行する際の標準的な損失（クエリ数 $q$ に比例する項など）に留まり、実用的なパラメータ設定を妨げるほどではありません。

5. 意義 (Significance)

• ポスト量子通信の信頼性向上: Signal プロトコルなどの実用的なメッセージングシステムをポスト量子化するための基盤技術であるリング署名の、量子攻撃に対する厳密な安全性が初めて確立されました。これにより、「harvest-now-decrypt-later」攻撃だけでなく、「harvest-now-judge-later」攻撃（匿名性の侵害）に対しても理論的に堅牢なシステム構築が可能になります。
• 証明技術の革新: 量子オラクルモデルにおける分布スイッチングとレニー分散の扱いに関する新たな知見は、リング署名だけでなく、他のポスト量子暗号（Falcon 署名など）の安全性証明にも応用可能な汎用的な技術です。
• 標準化への寄与: NIST などの標準化機関がポスト量子暗号を評価する際、QROM での証明は必須要件となりつつあります。本研究は、実用的なリング署名構成がこれらの要件を満たすことを示す重要なステップです。

要約すると、この論文は「量子オラクル分布スイッチング」という新しい理論的枠組みを開発し、それを用いてポスト量子リング署名の主要な構成要素を QROM において厳密に安全であることを証明した画期的な研究です。