論文の概要: On the Limits of Stretching Quantum Pseudorandomness
- arxiv url: http://arxiv.org/abs/2606.24736v1
- Date: Tue, 23 Jun 2026 16:00:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-24 22:16:49.045662
- Title: On the Limits of Stretching Quantum Pseudorandomness
- Title（参考訳）: ストレッチ量子擬似性限界について
- Authors: Boyang Chen, Andrea Coladangelo, Yao-Ting Lin, Nikos Skoumios, Justin Tysdal, Yiming Wang,
- Abstract要約: 擬似乱数状態は古典的擬似乱数生成子の量子アナログである。
単一コピー型セキュア擬似乱数状態間の出力長の異なる最初のブラックボックス分離を証明した。
- 参考スコア（独自算出の注目度）: 7.528006499174231
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Pseudorandom states, introduced by Ji, Liu, and Song (CRYPTO '18), are quantum analogues of classical pseudorandom generators. A fundamental property of classical pseudorandom generators is that their output can be stretched to arbitrary polynomial length. Whether an analogous stretching property holds for quantum pseudorandom states remains unclear. In this work, we prove the first black-box separation between single-copy secure pseudorandom states ($\mathsf{1PRS}$) with different output lengths. Specifically, we construct a quantum oracle relative to which $\mathsf{1PRS}$ with output length $m(n)=1.1n$ exist, but $\mathsf{1PRS}$ with output length $m(n)=Ω(n^{2+ε})$ do not, for any $ε>0$. Our proof leverages the Common Haar Random State (CHRS) model introduced by Chen, Coladangelo, and Sattath (EUROCRYPT '25), and introduces a technique to bound the effective number of resource CHRS states utilized by any $\mathsf{1PRS}$ generator in this model.
- Abstract（参考訳）: Ji, Liu, and Song (CRYPTO '18) によって導入された擬似ランダム状態は、古典的擬似ランダム生成子の量子類似体である。
古典的擬似乱数生成の基本的な性質は、それらの出力が任意の多項式長にまで拡張できることである。
類似のストレッチ特性が量子擬似ランダム状態に対して成立するかどうかはまだ不明である。
本研究では、単一コピーの安全な擬似ランダム状態(\mathsf{1PRS}$)間の最初のブラックボックス分離を異なる出力長で証明する。
具体的には、出力長 $m(n)=1.1n$ を持つ $\mathsf{1PRS}$ を相対的に構成するが、出力長 $m(n)=Ω(n^{2+ε})$ は任意の $ε>0$ に対して存在しない。
本稿では,Chen,Coladangelo,Sattathが導入したCHRS(Common Haar Random State)モデル(EUROCRYPT '25)を活用し,任意の$\mathsf{1PRS}$ジェネレータが利用する資源CHRS状態の有効個数をバインドする手法を提案する。
関連論文リスト
- Rényi divergence-based uniformity guarantees for $k$-universal hash functions [53.80737717363129]
普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。
ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
論文 参考訳（メタデータ） (2024-10-21T19:37:35Z) - Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。
我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
論文 参考訳（メタデータ） (2024-04-25T17:08:34Z) - Simple constructions of linear-depth t-designs and pseudorandom unitaries [40.72668922727092]
一様ランダムなユニタリ、すなわちハール測度から引き出されたユニタリは、多くの有用な性質を持つが、効率的に実装することはできない。
$t-設計はハール測度の最初の$tモーメントを再現するランダムユニタリーであり、擬ランダムユニタリー(PRU)はハール測度と計算的に区別できないランダムユニタリーである。
論文 参考訳（メタデータ） (2024-04-19T06:13:02Z) - Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
計算基底の部分集合である$S$に対する部分集合状態は [ frac1sqrt|S|sum_iin S |irangle である。
固定された部分集合サイズ $|S|=s$ に対して、$s = 2n/omega(mathrmpoly(n))$ と $s=omega(mathrmpoly(n))$ が与えられたとき、ランダムな部分集合状態は情報理論上はHaarランダム状態と区別できないことを示す。
論文 参考訳（メタデータ） (2023-12-23T15:52:46Z) - On the Computational Hardness of Quantum One-Wayness [3.3315839189695167]
Pseudorandom状態は、$n$bitsを$log n + 1$ qubitsに圧縮する。
一方向のステートジェネレータは、古典的に$rmPP$oracleにアクセスできる量子アルゴリズムによって破壊することができる。
我々の結果の興味深い意味は、すべての$t(n) = o(n/log n)$に対して、$t(n)$-copy 1-way状態生成器が無条件に存在することである。
論文 参考訳（メタデータ） (2023-12-13T18:56:03Z) - Quantum Cryptography in Algorithmica [0.7524721345903025]
ブラックボックス設定では、一方の関数が存在しなくても擬似ランダム状態に基づく量子暗号が可能であることを示す。
また、我々の結果をマルチコピー安全な擬似ランダム状態に一般化する予想も導入する。
論文 参考訳（メタデータ） (2022-12-01T21:33:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。