論文の概要: Lower Bounds for Preprocessing Attacks on Quantum Cryptography
- arxiv url: http://arxiv.org/abs/2610.02101v2
- Date: Sat, 03 Oct 2026 05:14:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-07 04:43:28.528452
- Title: Lower Bounds for Preprocessing Attacks on Quantum Cryptography
- Title（参考訳）: 量子暗号における前処理攻撃の下位境界
- Abstract要約: ランダムオラクルモデルにおいて、量子暗号に対する前処理攻撃に対して、ほぼ均一な下界を証明した。
対照的に、量子後片道関数の最もよく知られた境界は$O(fracT2N + sqrtfracSTN)$で、自明な攻撃は$S = N$である。
- 参考スコア（独自算出の注目度）: 2.9177105867949886
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a $T$-query adversary with $S$ qubits of non-uniform advice can recover a random key $k$ from the $n$-qubit binary phase state $|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$. In contrast, the best known bound for post-quantum one-way functions is $O(\frac{T^2 + ST}{N})$, with a trivial attack at $S = N$. This demonstrates a new advantage of quantum cryptography over classical cryptography: $n$ qubits of communication suffice for security against preprocessing attacks with space up to $N^2$ rather than $N$. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of $O(\frac{T^2}N + \sqrt{\frac{ST}N})$. (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight $O(\frac{\sqrt{S}}N)$ bound for the pseudorandomness of random binary phase states against space $S$ distinguishers.
- Abstract（参考訳）: ランダムオラクルモデルにおいて、量子暗号に対する前処理攻撃に対して、ほぼ最適の下位境界を証明した。
具体的には、$T$-query adversary with $S$ qubits of non-uniform advice can recover a random key $k$ from the $n$-qubit binary phase state $|\_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$。
対照的に、量子後片道関数の最もよく知られた境界は$O(\frac{T^2 + ST}{N})$であり、自明な攻撃は$S = N$である。
これは、古典暗号よりも量子暗号の新たな利点を示している:$n$ qubitsの通信は、$N$ではなく$N^2$までのスペースを持つ前処理攻撃に対するセキュリティのために十分である。
我々の手法は単純で、ランダム行列の演算ノルムとして最適前処理攻撃を表現し、この値をトレースモーメント法を介してランダムオラクルに限定する。
これらのトレースモーメントは、圧縮オラクル(Zhandry, Crypto 2019)を使って自然な解釈を行い、分析します。
これは、前処理攻撃に対するポスト量子暗号の安全性を証明するためのLiu(Eurocrypt 2023)のアプローチの単純化と一般化であると見なすことができる。
1) QROM における量子後 PRG の解析を厳格化し、$O(\frac{T^2}N + \sqrt {\frac{ST}N})$ の区別可能な優位性を実現する。
2) ユニタリ合成では,ロムバルディ・マライト(STOC 2024)の1クエリの下限を拡張して,任意の関数クエリを1つの任意の関数クエリと,関数クエリの前後で,ランダムなオラクルに対する多項式的な多数の(適応的な)クエリに保持できる敵に対して保持する。
これはまた、オリジナルのLMW24の結果を圧縮オラクルの言葉で解釈する。
(3) 最後に、空間$S$微分子に対してランダム二元相状態の擬ランダム性に対して、厳密な$O(\frac{\sqrt{S}}N)$を証明した。
関連論文リスト
- Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。
我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
論文 参考訳（メタデータ） (2026-09-30T17:51:21Z) - Computational Bounds for $f$-Routing [1.2604738912025477]
我々は、一様攻撃者に対する無条件リソースの低い境界を証明した。
入力長 $n$ と十分小さい定数 $>0$ に対して、$q$ qubits を用いた一様生成戦略は、以下の計算境界を$f$ で表している。
これらの境界は、内積関数 $f=mathrmIP$ に対して、Bluhm, Christandl, Speelman (2022) の$qlelog n$ を超える。
論文 参考訳（メタデータ） (2026-09-30T17:46:42Z) - Beyond NISQ Assumptions: One-time Memory in the Classically Accessible Random-Oracle Model [5.865029600972317]
我々は, [BDF+11] や [AK22] のように古典的にアクセス可能なランダムオラクルモデル (CAROM) を適用する。
シミュレーション・セキュアな1時間メモリ(OTM)をCAROM下で実現可能であることを示す。
論文 参考訳（メタデータ） (2026-09-26T13:22:30Z) - Quantum Advantage in Tolerant Junta Testing [0.5442955439283729]
適応設定において、許容値$k$-juntaテスト問題に対する最初の超多項式量子優位性を確立する。
特定のパラメータ体系内では、高い精度で寛容な$k$-juntaテストが$mathrmpoly(k)$quantumquantumquantum(k)$で解けることを示す。
論文 参考訳（メタデータ） (2026-06-22T11:42:39Z) - Cloning Games, Black Holes and Cryptography [50.022147589030304]
クローンゲーム解析のための新しいツールキットを提案する。
このフレームワークにより、バイナリフェーズ状態に基づいて新しいクローンゲームを分析することができる。
連成位相の変分最適境界は、ブラックホールの理想化されたモデルで衝突する情報について定量的な洞察を与えることを示す。
論文 参考訳（メタデータ） (2024-11-07T14:09:32Z) - A one-query lower bound for unitary synthesis and breaking quantum
cryptography [7.705803563459633]
ユニタリ合成問題では、任意の$n$qubitのユニタリ$U$を、任意のブール関数$f$を計算するオラクルで拡張された効率的な量子$A$で実装できるかどうかを問う。
本研究は, 対向する$Af$の最大成功確率を解析することにより, 下位境界の証明を可能にする, 効率的なチャレンジャーアドゲームとしてのユニタリ合成を証明する。
論文 参考訳（メタデータ） (2023-10-13T05:39:42Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs [0.0]
ランダム関数 $f : [N] rightarrow [N]$ の衝突対を量子コンピュータを用いて探索する。
利用可能なメモリのサイズが制限された場合、関数に対するクエリの数は大幅に増加しなければなりません。
論文 参考訳（メタデータ） (2020-02-20T18:48:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。