論文の概要: 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) - MicroCrypt Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations [9.738636411374223]
量子暗号プリミティブの2つの自然な緩和について検討する。
1つ目は、ランダムに一様にサンプリングされるのではなく、量子アルゴリズムによって入力が生成される量子入力サンプリングである。
2つ目の緩和である $bot$-pseudodeterminism は、入力の逆多項式分数に対して出力を特別な記号 $bot$ にすることで決定論の要求を緩和する。
論文 参考訳（メタデータ） (2025-05-20T14:57:04Z) - PRS Length Expansion [4.31241676251521]
擬似ランダム量子状態(英: Pseudo-random quantum state、PRS)は、量子暗号における鍵となるプリミティブである。
この研究は、いくつかのPRS発生器を拡張できると推測し、いくつかの特定の例に対してそのような拡張の証明を提供する。
論文 参考訳（メタデータ） (2024-11-05T16:06:59Z) - 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) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - 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) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。
最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
論文 参考訳（メタデータ） (2020-07-23T10:50:42Z) - Scalable Pseudorandom Quantum States [14.048989759890476]
PRSジェネレータの既存の構成では、州内のキュービット数のセキュリティスケール、すなわち$n$-qubit PRSの(統計的な)セキュリティパラメータは、およそ$n$である。
量子セキュアな片方向関数は、スケーラブルなPSSを意味することを示す。
まず,ランダム関数へのオラクルアクセスが与えられると,そのランダム関数を量子セキュア(古典的)擬似ランダム関数に置き換えて,計算セキュリティを実現するというパラダイムを踏襲する。
論文 参考訳（メタデータ） (2020-04-04T17:15:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。