論文の概要: How to Build Pseudorandom Unitaries in Microcrypt
- arxiv url: http://arxiv.org/abs/2610.03711v1
- Date: Fri, 02 Oct 2026 17:58:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-06 00:14:30.558688
- Title: How to Build Pseudorandom Unitaries in Microcrypt
- Title（参考訳）: Pseudorandom Unitaryをマイクロ暗号化で構築する方法
- Abstract要約: 擬似乱数ユニタリ(PRU)は量子計算可能な一方向関数なしで存在することを証明している。
この結果は、PRUが量子計算可能な片方向関数を含まないという古典的な証拠を与える。
- 参考スコア（独自算出の注目度）: 7.682244137762325
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide the first evidence relative to a classical oracle that pseudorandom unitaries (PRUs) can exist without quantum-computable one-way functions. To obtain this result, we first prove that five independent random diagonal phase layers interleaved with Hadamard transforms \[ U=F_5HF_4HF_3HF_2HF_1 \] form a strong PRU with security under adaptive, controlled access to the unitary, its inverse, transpose, and complex conjugate. Our main result is that, when the phase layers are implemented using a classical random oracle O, the construction remains secure against uniform BQP adversaries with coherent access to suitable Boolean completions of classical-input $QMA^{PH}^{O}}$ decision problems. Such an adversary can invert (even quantum-computable) one-way functions and solve efficiently verifiable one-way puzzles defined relative to O. Our result therefore provides classical-oracle evidence that PRUs do not imply quantum-computable one-way functions, in the form of a black-box separation. We substantially strengthen the classical-oracle result of Kretschmer, Qian, and Tal (STOC 2025) by obtaining PRUs secure against these QMA-aided adversaries. Our construction also consists of a simple, efficient circuit that queries a random function, suggesting a route to concrete implementation via the random-oracle heuristic.
- Abstract（参考訳）: 量子計算可能な片方向関数を使わずに擬似ランダムユニタリ(PRU)が存在するという古典的なオラクルに対する最初の証拠を提供する。
この結果を得るために、アダマール変換にインターリーブされた5つの独立したランダムな対角相層が、適応的、制御されたユニタリ、その逆転位、転位、複素共役を持つ強力なPRUを形成することを最初に証明した。
我々の主な結果は、位相層が古典的ランダムオラクルOを用いて実装されている場合、構成は古典的入力の$QMA^{PH}^{O}} の適切なブール完備化にコヒーレントなアクセスを持つ一様BQP敵に対して安全であり続けることである。
したがって、この結果から、PRUはブラックボックス分離の形で量子計算可能なワンウェイ関数を含まないという古典的な証拠が得られる。
我々は,これらのQMA支援敵に対するPRUの確保により,Kretschmer,Qian,Tal(STOC 2025)の古典的オーラル結果を大幅に強化する。
我々の構成は、ランダム関数を問合せする単純で効率的な回路で構成されており、ランダム・オークル・ヒューリスティックによる具体的な実装への道筋を示唆している。
関連論文リスト
- Succinct Arguments for QMA in the Quantum Random Oracle Model [50.20559283775139]
量子乱数オラクルモデル(QROM)におけるQMAの最初の簡潔な議論を、暗号的仮定や証明されていない予想に頼ることなく構築する。
我々の結果は、量子インタラクティブなオラクル証明(QIOP)を同じ言語の量子引数にコンパイルする効率保存変換である。
論文 参考訳（メタデータ） (2026-09-29T12:54:55Z) - (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
微分可能性(Indifferentiability)は、理想的なオブジェクトのセキュリティを分析するための暗号パラダイムである。
その強さにもかかわらず、前処理攻撃に対するセキュリティを提供する無差別性は知られていない。
本稿では、構成可能であるだけでなく、任意の事前計算を考慮に入れた微分可能性の強化を提案する。
論文 参考訳（メタデータ） (2024-10-22T00:41:47Z) - How to Construct Random Unitaries [2.8237889121096034]
量子セキュアな片方向関数が存在すると仮定して、PRUが存在することを証明する。
本研究では,Haar-randomユニタリに対するクエリを量子コンピュータ上で効率的にシミュレートできることを証明した。
論文 参考訳（メタデータ） (2024-10-14T03:07:36Z) - Pseudorandom unitaries with non-adaptive security [43.15464425520681]
本稿では、ランダムなクリフォードユニタリ、擬似乱数二相演算子、擬似乱数置換演算子の結合であるPRU構成を提案する。
このPRU構造は、量子セキュア片方向関数の存在を前提として、非適応微分器に対して安全であることを示す。
論文 参考訳（メタデータ） (2024-02-22T18:56:37Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - Coherent randomized benchmarking [68.8204255655161]
独立サンプルではなく,異なるランダム配列の重ね合わせを用いることを示す。
これは、ベンチマーク可能なゲートに対して大きなアドバンテージを持つ、均一でシンプルなプロトコルにつながることを示す。
論文 参考訳（メタデータ） (2020-10-26T18:00:34Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - A Note on Quantum-Secure PRPs [10.699704508276174]
敵が置換をクエリできる場合でも、セキュアな擬似乱数置換を構築する方法を示す。
このような量子セキュアなRPPは、暗号や複雑性理論に多くの応用を見出した。
論文 参考訳（メタデータ） (2016-11-17T05:09:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。