論文の概要: Separating Pseudorandom Generators from Logarithmic Pseudorandom States

• arxiv url: http://arxiv.org/abs/2510.20131v1
• Date: Thu, 23 Oct 2025 02:09:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:17.133743
• Title: Separating Pseudorandom Generators from Logarithmic Pseudorandom States
• Title（参考訳）: 対数的擬似乱数状態からの擬似乱数発生器の分離
• Authors: Mohammed Barhoush,
• Abstract要約: 我々は、(量子評価可能な)PRGとPRSの量子ブラックボックス分離を確立する。 デジタルシグネチャや量子公開鍵暗号を含む対数PSSで示されるいくつかのプリミティブとPRGを分離する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Pseudorandom generators (PRGs) are a foundational primitive in classical cryptography, underpinning a wide range of constructions. In the quantum setting, pseudorandom quantum states (PRSs) were proposed as a potentially weaker assumption that might serve as a substitute for PRGs in cryptographic applications. Two primary size regimes of PRSs have been studied: logarithmic-size and linear-size. Interestingly, logarithmic PRSs have led to powerful cryptographic applications, such as digital signatures and quantum public-key encryption, that have not been realized from their linear counterparts. However, PRGs have only been black-box separated from linear PRSs, leaving open the fundamental question of whether PRGs are also separated from logarithmic PRSs. In this work, we resolve this open problem. We establish a quantum black-box separation between (quantum-evaluable) PRGs and PRSs of either size regime. Specifically, we construct a unitary quantum oracle with inverse access relative to which no black-box construction of PRG from (logarithmic or linear) PRS exists. As a direct corollary, we obtain separations between PRGs and several primitives implied by logarithmic PRSs, including digital signatures and quantum public-key encryption.
• Abstract（参考訳）: Pseudorandom generators (PRG) は古典暗号の基本的プリミティブであり、幅広い構成を支えている。 量子設定において、擬似ランダム量子状態(PRS)は、暗号アプリケーションにおけるPRGの代用として機能する可能性のある、潜在的に弱い仮定として提案された。 PRSの2つの主要なサイズレギュレーション、すなわち対数サイズと線形サイズが研究されている。 興味深いことに、対数PSSは、デジタルシグネチャや量子公開鍵暗号のような強力な暗号アプリケーションに導かれており、それらの線形暗号からは実現されていない。 しかしながら、PRGは線形PRSから分離されたブラックボックスのみであり、PRGが対数PRSから分離されているかどうかという根本的な疑問が残る。 この作業では、このオープンな問題を解決します。 我々は、(量子評価可能な)PRGとPRSの量子ブラックボックス分離を確立する。 具体的には、(対数的あるいは線形)PRGのブラックボックス構成が存在しない逆アクセスを持つユニタリ量子オラクルを構築する。 直接系として、デジタル署名や量子公開鍵暗号を含む対数的PSSによって暗示されるPRGといくつかのプリミティブの分離を得る。

関連論文リスト

• PRS Length Expansion [4.31241676251521]
  擬似ランダム量子状態(英: Pseudo-random quantum state、PRS)は、量子暗号における鍵となるプリミティブである。 この研究は、いくつかのPRS発生器を拡張できると推測し、いくつかの特定の例に対してそのような拡張の証明を提供する。
  論文  参考訳（メタデータ） (2024-11-05T16:06:59Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  我々は、ハミルトニアン相状態(HPS)問題と呼ばれる量子硬度仮定を導入する。 我々は、我々の仮定が少なくとも完全に量子的であることを示し、すなわち片方向関数を構成するのに使用できない。 仮定とその変形により、多くの擬似ランダム量子プリミティブを効率的に構築できることを示す。
  論文  参考訳（メタデータ） (2024-10-10T16:10:10Z)
• Geometric structure and transversal logic of quantum Reed-Muller codes [51.11215560140181]
  本稿では,量子リード・ミュラー符号(RM)のゲートを,古典的特性を利用して特徴付けることを目的とする。 RM符号のための安定化器生成器のセットは、特定の次元のサブキューブに作用する$X$と$Z$演算子によって記述することができる。
  論文  参考訳（メタデータ） (2024-10-10T04:07:24Z)
• Pseudorandom unitaries with non-adaptive security [43.15464425520681]
  本稿では、ランダムなクリフォードユニタリ、擬似乱数二相演算子、擬似乱数置換演算子の結合であるPRU構成を提案する。 このPRU構造は、量子セキュア片方向関数の存在を前提として、非適応微分器に対して安全であることを示す。
  論文  参考訳（メタデータ） (2024-02-22T18:56:37Z)
• Quantum Pseudorandomness Cannot Be Shrunk In a Black-Box Way [0.0]
  Pseudorom Quantum States (PRS) は、Ji, Liu, Songによって、Pseudorandom Generatorsと類似した量子として導入された。 対数サイズの出力を持つPSSであるショートPRSは、暗号アプリケーションとともに文献に導入されている。 ここでは、擬似ランダム性を維持しながら、2021年から対数量子ビット長までPSSの出力を縮小することは不可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-20T19:02:43Z)
• Signatures From Pseudorandom States via $\bot$-PRFs [0.11650821883155184]
  我々は $bot$-PRG と $bot$-PRF の新たな定義を導入する。 私たちの主な応用は、古典的な公開鍵と署名を備えた(量子)デジタル署名スキームです。
  論文  参考訳（メタデータ） (2023-11-01T20:54:50Z)
• Quantum simulation of $\phi^4$ theories in qudit systems [53.122045119395594]
  回路量子力学(cQED)システムにおける格子$Phi4$理論の量子アルゴリズムの実装について論じる。 quditシステムの主な利点は、そのマルチレベル特性により、対角的な単一量子ゲートでしかフィールドの相互作用を実装できないことである。
  論文  参考訳（メタデータ） (2021-08-30T16:30:33Z)
• A Note on Quantum-Secure PRPs [10.699704508276174]
  敵が置換をクエリできる場合でも、セキュアな擬似乱数置換を構築する方法を示す。 このような量子セキュアなRPPは、暗号や複雑性理論に多くの応用を見出した。
  論文  参考訳（メタデータ） (2016-11-17T05:09:48Z)

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

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