論文の概要: Quantum Security of XOR of Permutations via Fourier Analysis

• arxiv url: http://arxiv.org/abs/2609.34413v1
• Date: Mon, 28 Sep 2026 06:29:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 20:59:30.447277
• Title: Quantum Security of XOR of Permutations via Fourier Analysis
• Title（参考訳）: フーリエ解析による置換XORの量子セキュリティ
• Abstract要約: 我々は、$rge 2$$$$0,1n$以上のランダムな置換の XOR が、任意の$q$-query量子アルゴリズムによってランダム関数と区別できないことを証明した。 これは、誕生日限定セキュリティの量子バージョンを達成する置換による最初の構成である。 また、範囲が$qle 2n/2$ と $approx 2n$ であることを示すいくつかの攻撃も提示する。
• 参考スコア（独自算出の注目度）: 3.942458378599431
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The XOR of two or more independent random permutations (XoP) is the prototypical pseudorandom function built from permutations achieving security beyond the birthday bound. The classical security of the XoP construction is well established, but its security against quantum attacks that query XoP in superposition has remained widely open. We prove that the XOR of $r\ge 2$ random permutations over $\{0,1\}^n$ is indistinguishable from a random function by any $q$-query quantum algorithm with advantage \[O\left(\min\left\{\frac{q^3}{2^{rn}},\frac{q^{1.5}}{2^{(r-0.5)n}},\frac{1}{2^{(r-1.5)n}}\right\}\right)\] for all $q\ll 2^n$. In particular, XoP remains secure throughout the entire query range, far beyond the $2^{n/3}$ bound due to quantum collision finding attacks. This is the first construction from permutations that achieves the quantum version of the beyond birthday bound security. We also present several heuristic attacks suggesting the tightness of our bounds in ranges $q\le 2^{n/2}$ and $\approx 2^n$. We use a Fourier-analytic variant of the polynomial method: the advantage of any $q$-query quantum algorithm is controlled by the Fourier components of degree at most $2q$, or by $2q$ input-output data of the construction. The norms of most components are bounded well, proving the bound $2^{-(r-3/2)n}$. The norm of low-degree components turn out to be too large for the bounds $q^3/2^{rn}$ and $q^{1.5}/2^{(r-0.5)n}$. We reinterpret these low-degree components as (sums of) advantages of the other problems. For example, the degree-2 and degree-4 terms are interpreted as the advantages against random functions with and without \emph{planted collisions}, which in turn are bounded using Zhandry's small-range distributions. Along the way, we prove a new bound for the small-range indistinguishability for (ironically) large ranges, which is of independent interest.
• Abstract（参考訳）: 2つ以上の独立な乱数置換 (XoP) の XOR は、誕生日境界を超えたセキュリティを達成するために置換から構築された原型的擬似乱数関数である。 XoPの構造の古典的なセキュリティは確立されているが、XoPをスーパーポジションでクエリする量子攻撃に対するセキュリティは、広く開放されている。 xOR of $r\ge 2$ random permutations over $\{0,1\}^n$ is indistinguishable to a random function by any $q$-query quantum algorithm with advantage \[O\left(\min\left\{\frac{q^3}{2^{rn}},\frac{q^{1.5}}{2^{(r-0.5)n}},\frac{1}{2^{(r-1.5)n}}\right\right)\] for all $q\ll 2^n$。 特に、XoPは、量子衝突による攻撃により、クエリ範囲全体にわたって安全であり、$2^{n/3}$を超える。 これは、誕生日限定セキュリティの量子バージョンを達成する置換による最初の構成である。 また、範囲が$q\le 2^{n/2}$ と $\approx 2^n$ であることを示すいくつかのヒューリスティックな攻撃も提示する。 任意の$q$-query量子アルゴリズムの利点は、次数2q$または2q$の入力出力データによって制御される。 ほとんどの成分のノルムは有界であり、 2^{-(r-3/2)n}$ が有界であることを証明する。 低次成分のノルムは、境界の$q^3/2^{rn}$と$q^{1.5}/2^{(r-0.5)n}$には大きすぎる。 我々はこれらの低次成分を他の問題の利点として再解釈する。 例えば、次数 2 と次数 4 の項は、ランダムな関数に対して \emph{planted collisions} をもたない利点として解釈され、これは Zhandry の小さな範囲分布を用いて有界である。 その過程で、我々は(偶然に)独立した興味を持つ広い範囲の小さな範囲の区別不可能性に対する新しい境界を証明した。

関連論文リスト

• Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security [2.3865782873384576]
  独立な乱数置換と関連する置換から関数への変換の和について検討する。 我々は,その構成を確率密度で表現し,受容関数で区別する統一されたフーリエ解析処理を行う。
  論文  参考訳（メタデータ） (2026-09-28T15:30:40Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry [0.0]
  for general max-k-XORSAT with $k geq 3$, no-time algorithm can be significantly better than random guessing on worst-case instance。 この接続を明示的にし、任意の有限体上の有界次数$D$および有界次数$E$k$-LINSAT$(q,r)$にハードネスを拡張する。
  論文  参考訳（メタデータ） (2026-06-11T16:59:12Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。 我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
  論文  参考訳（メタデータ） (2024-04-25T17:08:34Z)
• On the average-case complexity of learning output distributions of quantum circuits [33.76498647184212]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• On the moments of random quantum circuits and robust quantum complexity [0.0]
  我々は、ロバスト量子回路の複雑さの増大に新たな低い境界を証明した。 局所ゲートを持つランダム量子回路に対して、$SU(4)$の部分群から引き出された2つの境界を示す。
  論文  参考訳（メタデータ） (2023-03-29T18:06:03Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)

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

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