論文の概要: Black-Box Separation Between Pseudorandom Unitaries, Pseudorandom Isometries, and Pseudorandom Function-Like States

• arxiv url: http://arxiv.org/abs/2510.04486v1
• Date: Mon, 06 Oct 2025 04:50:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 16:52:59.682751
• Title: Black-Box Separation Between Pseudorandom Unitaries, Pseudorandom Isometries, and Pseudorandom Function-Like States
• Title（参考訳）: Pseudorom Unitary, Pseudorom Isometries, および Pseudorom Function-like States間のブラックボックス分離
• Authors: Aditya Gulati, Yao-Ting Lin, Tomoyuki Morimae, Shogo Yamada,
• Abstract要約: Pseudorandom関数(PRF)は古典暗号における最も基本的なプリミティブの1つである。 量子暗号では、PRFは存在せず、それらの量子アナログが存在する可能性がある。 本稿では、これらの自然量子アナログが等価であるかどうかを部分的に解決する。
• 参考スコア（独自算出の注目度）: 6.67838905076129
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Pseudorandom functions (PRFs) are one of the most fundamental primitives in classical cryptography. On the other hand, in quantum cryptography, it is possible that PRFs do not exist but their quantum analogues could exist, and still enabling many applications including SKE, MACs, commitments, multiparty computations, and more. Pseudorandom unitaries (PRUs) [Ji, Liu, Song, Crypto 2018], pseudorandom isometries (PRIs) [Ananth, Gulati, Kaleoglu, Lin, Eurocrypt 2024], and pseudorandom function-like state generators (PRFSGs) [Ananth, Qian, Yuen, Crypto 2022] are major quantum analogs of PRFs. PRUs imply PRIs, and PRIs imply PRFSGs, but the converse implications remain unknown. An important open question is whether these natural quantum analogues of PRFs are equivalent. In this paper, we partially resolve this question by ruling out black-box constructions of them: 1. There are no black-box constructions of $O(\log\lambda)$-ancilla PRUs from PRFSGs. 2. There are no black-box constructions of $O(\log\lambda)$-ancilla PRIs with $O(\log\lambda)$ stretch from PRFSGs. 3. There are no black-box constructions of $O(\log\lambda)$-ancilla PRIs with $O(\log\lambda)$ stretch from PRIs with $\Omega(\lambda)$ stretch. Here, $O(\log\lambda)$-ancilla means that the generation algorithm uses at most $O(\log\lambda)$ ancilla qubits. PRIs with $s(\lambda)$ stretch is PRIs mapping $\lambda$ qubits to $\lambda+s(\lambda)$ qubits. To rule out the above black-box constructions, we construct a unitary oracle that separates them. For the separations, we construct an adversary based on the quantum singular value transformation, which would be independent of interest and should be useful for other oracle separations in quantum cryptography.
• Abstract（参考訳）: Pseudorandom関数(PRF)は、古典暗号における最も基本的なプリミティブの1つである。 一方、量子暗号では、PRFは存在せず、それらの量子アナログが存在する可能性があり、SKE、MAC、コミットメント、マルチパーティ計算など、多くのアプリケーションを可能にする。 Pseudorandom Unitary (PRUs) [Ji, Liu, Song, Crypto 2018], pseudorandom isometries (PRIs) [Ananth, Gulati, Kaleoglu, Lin, Eurocrypt 2024], pseudorandom function-like state generators (PRFSGs) [Ananth, Qian, Yuen, Crypto 2022]はPRFの主要な量子アナログである。 PRUはPRIを、PRIはPRFSGを暗示するが、逆の意味はいまだ不明である。 重要なオープンな疑問は、これらの自然量子類似体が等価であるかどうかである。 本稿では, PRFSGsから$O(\log\lambda)$-ancilla PRUのブラックボックス構造は存在しない。 2.$O(\log\lambda)$-ancilla PRIsと$O(\log\lambda)$ stretch from PRFSGsのブラックボックス構造はありません。 3.$O(\log\lambda)$-ancilla PRIsと$O(\log\lambda)$ stretch from PRIs with $\Omega(\lambda)$ stretchのブラックボックス構造はありません。 ここで、$O(\log\lambda)$-ancillaは、生成アルゴリズムが少なくとも$O(\log\lambda)$ ancilla qubitsを使用することを意味する。 $s(\lambda)$ stretchのPRIは、$\lambda$ qubitsを$\lambda+s(\lambda)$ qubitsにマッピングする。 上記のブラックボックス構造を除外するために、それらを分離するユニタリオラクルを構築する。 分離のためには、量子特異値変換に基づく逆数を構築し、これは興味のないものであり、量子暗号における他のオラクル分離に有用である。

関連論文リスト

• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Pseudorandom Isometries [6.0709446838151715]
  我々は$cal Q$-secure pseudorandom isometries (PRI)という新しい概念を導入する。 PRIは、$n$-qubit状態を$(n+m)$-qubit状態にマッピングする効率的な量子回路である。 我々は、量子擬似ランダム性の概念に対する長さ拡張定理を含む、PRIの多くの暗号的応用を実証する。
  論文  参考訳（メタデータ） (2023-11-06T06:27:14Z)
• Signatures From Pseudorandom States via $\bot$-PRFs [0.11650821883155184]
  我々は $bot$-PRG と $bot$-PRF の新たな定義を導入する。 私たちの主な応用は、古典的な公開鍵と署名を備えた(量子)デジタル署名スキームです。
  論文  参考訳（メタデータ） (2023-11-01T20:54:50Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。 我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。 補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
  論文  参考訳（メタデータ） (2020-09-29T08:41:53Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。