技術要約：関数型疑似乱数ユニタリによる疑似乱数量子プロセスの生成

問題定義

ハール乱数ユニタリは、デカップリング、情報のスクランブリング、量子暗号などの現象の基礎となる、一般的なランダム量子進化の標準的なモデルである。しかし、典型的なハール乱数ユニタリは指数関数的な記述量と回路複雑性を持ち、実用的な実装は困難である。疑似乱数ユニタリ（PRU）は、単一のランダムに見える進化に対しては効率的な代替手段を提供するが、多くの暗号的および物理的なタスクでは、公開されたコンテキスト（例：ナンス、レジスタ幅、またはタイムステップ）によってインデックス付けされた、独立してランダムに見える操作の「ファミリー」を必要とする。

このようなファミリーを生成するための既存のアプローチ（各コンテキストに対して独立したPRUキーをサンプリングする方法など）は、大規模かつ動的に増大する秘密キー集合の管理オーバーヘッドのために非実用的である。さらに、標準的なPRUは、アドバーサリがファミリーの複数のインスタンスと相互作用する場合の適応的な量子クエリに対するセキュリティを本質的に提供しない。本論文は、単一の短いマスターキーから、適応的にアドレス指定可能な疑似乱数ユニタリの全ファミリーを生成しつつ、アドバーサリがファミリーを適応的かつコヒーレントにクエリする場合に対してもセキュリティを維持するプリミティブの必要性に対処するものである。

手法

著者らは、単一のキー $k$ と公開ラベル $x$ によって、効率的に実装可能なユニタリを決定する鍵付きファミリー $\{G_k(x)\}_{x \in \mathcal{X}_\lambda}$ である**疑似乱数関数型ユニタリ（PRFU）**を導入する。セキュリティ目標は、各ラベル $x$ が独立にサンプリングされたハール乱数ユニタリ $H_x$ に写像される、関数型ハール乱数ファミリーからの計算量的区別不能性である。

本論文では、ラベル $x$ のアクセスモデルとして以下の2つを区別している：

1. 古典的ラベル・アクセス（Classical-label access）： ラベルは古典的なビット列として供給される。データおよび参照レジスタは量子状態である。
2. コヒーレント・ラベル・アクセス（Coherent-label access）： ラベルは量子レジスタ $L$ 内に供給され、重ね合わせ状態や他のレジスタとの絡み合い状態にある可能性がある。オラクルは制御ユニタリ $W_k = \sum_x |x\rangle\langle x|_L \otimes G_k(x)$ を適用する。

構成

1. 古典的ラベル構成：
著者らは、ポスト量子疑似乱数関数（PRF）$F_k$ と適応的フォワードPRUファミリー $\{V_a\}$ を組み合わせた汎用的な構成を提案している。この構成は次のように定義される：
$$G_k(x) := V_{F_k(x)}$$
ここで、PRFは内側のPRUのシード $a = F_k(x)$ を導出する。セキュリティ証明には、「遅延テーブル（deferred table）」ハイブリッド引数を用い、ラベルの初出現の順序に従って処理を行う。重要な構成要素は、中間ハイブリッドをシミュレートするために、増幅された相対誤差を持つ置換関数クリフォード（PFC）設計から導出された**効率的に実装可能なハール近似（Haar proxy）**の使用である。これにより、内側のPRUがすべての可能なクエリに対して完全なハール近似である必要はなく、アドバーサリが行う限定された数のクエリに対してのみ近似であればよいという条件下で、識別優位性を抑えるための簡約が可能になる。

2. コヒーレント・ラベル構成：
コヒーレント・アクセスのために、著者らはインデックス付きPFCアンサンブルを直接用いてPRFUを構築する。ラベル $x$ を介してキーを導出するのではなく、ラベル $x$ を位相および置換プリミティブに直接組み込む。この構成は以下を用いる：

• 位相層のための量子安全な疑似乱数関数（qPRF） $g_{k_\Phi}(x, z)$
• 置換層のための、変更可能（tweakable）なインプレイス疑似乱数置換（qPRP） $\Pi_{k_P}(x, z)$
• 共有ユニタリ2デザイン $C$
  結果としてのユニタリは $W_k^{coh} = \hat{P}_{\Pi} \hat{\Phi}_{g} (I_L \otimes C)$ である。
  セキュリティは、**インデックス付きパス記録（indexed path-recording）**技術を用いて確立される。この手法は、ラベルの重ね合わせを含むクエリの履歴を追跡して干渉を分析する。証明により、理想的なインデックス付きPFCアンサンブルは、クエリ数 $q$ および $N=2^n$ に対して $2q(q-1)/(N+1)$ の範囲内で、独立したハールユニタリから統計的に区別不能であることが示される。計算的セキュリティは、ランダムなプリミティブを量子安全な対応物で置き換えることによって得られる。

量子プロセスへの拡張

本論文は、PRFUを疑似乱数量子チャネルおよび量子コーム（内部メモリを持つプロセス）へと拡張する。

• チャネル： シュレディンガー・ストニースミル展開（Stinespring dilation）内でPRFUを適用し、環境を破棄することで、疑似乱数関数型チャネル（PRFC）を生成する。
• コーム： 量子コームの連続する「歯（operations）」に異なるPRFUラベルを割り当てることで、疑似乱数コームを構築する。これにより、アクセス不能なメモリを持つマルチタイムダイナミクスを、適応的な介入や同時実行セッションに対して安全にエミュレートすることが可能になる。

主な貢献

1. PRFUsの定義： 公開ラベルによってインデックス付けされた、ランダムに見えるユニタリのファミリーを生成する、疑似乱数関数型ユニタリの形式化。
2. 古典的ラベル構成とセキュリティ： ポスト量子PRFとPRUを用いた汎用的な構成の提案。ハイブリッド引数とハール近似を用いて、適応的な古典的ラベル・クエリに対する安全性を証明。
3. コヒーレント・ラベル構成とセキュリティ： qPRFと変更可能なインプレイスqPRPを用いた、インデックス付きPFCアンサンブルに基づく特定の構成。ラベルの重ね合わせと干渉を扱うための、インデックス付きパス記録によるセキュリティ証明。
4. プロセスのリフティング： PRFUを量子チャネルや量子コームへとリフトアップできることを示し、内部メモリを持つプロセスを、適応的および同時実行のインタラクションに対して保護することを示した。
5. 可変幅PRU： PRFUとユニタリ・グルーイング（gluing）を組み合わせることで、生成後にレジスタ幅を選択可能な、単一キーによるPRUファミリーを作成する手法。
6. 応用： 以下を含む具体的な応用を概説：
   • ナンス解決型量子認証。
   • コヒーレントにマスクされたQRAMクエリ（前方アクセス観測者からデータベースの内容を隠蔽する）。
   • ランダムなマルチタイムダイナミクスの効率的なエミュレーション。

結果

• セキュリティ境界： 古典的ラベルの場合、識別優位性は、PRFの優位性、PRUの優位性、およびハール近似誤差に依存する項（$2q\eta$）の和によって抑えられる。コヒーレント・ラベルの場合、理想的なハールファミリーとの統計的距離は $2q(q-1)/(N+1)$ であり、計算的セキュリティは基礎となるqPRFおよびqPRPの困難性に依存する。
• 効率性： これらの構成は効率的であり、セキュリティパラメータ $\lambda$ およびクエリ数に対して多項式時間および回路サイズを必要とする。
• 可変幅： グルーイング構成は、生成後に選択される多項式境界のレジスタ幅に対して、疑似乱数ユニタリを生成することに成功し、異なる幅の間でもセキュリティが維持される。

意義および主張

本論文は、量子的な疑似乱数の概念を、個別の操作から効率的に生成される、ランダムに見える一連の量子ダイナミクスへと拡張することを主張している。PRFUsを導入することで、著者らは単一のPRUと、高度な量子プロトコルに必要な再現可能でコンテキスト依存のランダムな進化との間のギャップを埋めている。

本研究のハイライトは以下の通りである：

• 単一キーパラダイム： 独立したPRUのサンプリングに伴うキー管理の問題を回避し、単一の短いマスターキーから、適応的にアドレス指定可能な疑似乱数ユニタリの全ファミリーを導出することが可能である。
• コヒーレント・セキュリティ： 特定のインデックス付きパス記録技術を用いることで、ラベルが重ね合わせ状態でクエリされる場合でも、より強力な要件であるコヒーレント・セキュリティを維持できる。
• プロセスのセキュリティ： このフレームワークは、内部メモリを持つ複雑な量子プロセス（チャネルおよびコーム）へと自然に拡張でき、ステップ間に介入したり同時実行セッションを実行したりするアドバーサリに対してセキュリティを提供する。

著者らは、古典的ラベルについては（PRFのリフティングを介して）PRUとPRFUsの関係は明確であるが、コヒーレント・ラベルについては、その構成が単一のPRUからの一般的な変換ではなく特定のプリミティブに依存しているため、関係は未解決の課題であると述べている。また、標準的な仮定から変更可能なインプレイスqPRPを構築することは、依然として具体的な未解決問題である。