Fugu-MT 論文翻訳(概要): Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security

論文の概要: Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security

arxiv url: http://arxiv.org/abs/2609.35421v1
Date: Mon, 28 Sep 2026 15:30:40 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-02 05:34:54.076261
Title: Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security
Title（参考訳）: 置換の総和の不明瞭性:古典的および量子的セキュリティへのフーリエ解析経路
Abstract要約: 独立な乱数置換と関連する置換から関数への変換の和について検討する。我々は,その構成を確率密度で表現し,受容関数で区別する統一されたフーリエ解析処理を行う。
参考スコア（独自算出の注目度）: 2.3865782873384576
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study classical and quantum indistinguishability of sums of independent random permutations and related transformations from permutations to functions. Let $G$ be a finite abelian group of order $N$, and let $π^k_+(x)=π_1(x)+\cdots+π_k(x)$ for $k\geq2$ independent uniform random permutations of $G$. We give a unified Fourier analytic treatment in which the construction is represented by its probability density and a distinguisher by its acceptance function, with the classical and quantum query models imposing different restrictions on the Fourier support of the latter. Classically, we obtain the bound $O_k(q/N^{k-1/2})$ for every $q<N$, and refine it below the birthday threshold to $O_k(q^2/N^k)$. In the quantum model, a simulation argument gives $O_k(N^{-(k-3/2)})$ for $q\leq(N-1)/2$, while Fourier interpolation gives concrete finite bounds up to $q\leq4N/15$ and the query-dependent bounds $O\left(\min\left\{N^{-1/2},q^3/N^2 + 1/N\right\}\right)$ and $O_k\left(\min\left\{q^3/N^k,N^{-(k-3/2)}\right\}\right)$, for $k=2$ and $k \geq 3$, respectively, throughout $1\leq q\leq(N-1)/2$. For $q = 1$, the first bound sharpens to $O(N^{-2})$. Over $G=\mathbb F_2^n$, a one-query Fourier attack matches the order of our one-query bound, while an $N/2$-query parity attack with advantage $1/2$ shows that our bounds reach the constant-advantage query threshold. We further study two variants of sum of permutations over binary vector spaces. First, we allow arbitrary surjective linear postprocessing, which includes truncation, and obtain classical and quantum bounds that retain the output-size dependence. Second, we analyse Dinur's variable-output single-permutation construction, $\mathsf{LXoP}$, for every fixed output width, and derive its classical and quantum security bounds; for one- and two-block outputs, we give concrete quantum security bounds.
Abstract（参考訳）: 独立な乱数置換の和と関連する置換から関数への変換の古典的および量子的区別可能性について検討する。 G$ を位数 $N$ の有限アーベル群とし、$π^k_+(x)=π_1(x)+\cdots+π_k(x)$ for $k\geq2$ の独立一様ランダム置換を$G$とする。我々は,その構成を確率密度で表現し,その受容関数で区別する統一されたフーリエ解析処理を,古典的および量子的クエリモデルにより,後者のフーリエ支持に異なる制約を課す。古典的には、すべての$q<N$に対して有界な$O_k(q/N^{k-1/2})$を取得し、誕生日閾値以下で$O_k(q^2/N^k)$に精製する。量子モデルでは、$O_k(N^{-(k-3/2)})$ for $q\leq(N-1)/2$, while Fourier interpolation gives concrete finite bounds to $q\leq4N/15$ and the query-dependent bounds $O\left(\min\left\{N^{-1/2},q^3/N^2 + 1/N\right\right)$ and $O_k\left(\min\left\{q^3/N^k,N^{-(k-3/2)}\right\right)$, for $k=2$と$k \geq 3$がそれぞれ$/2である。 q = 1$ の場合、最初の有界なシャープは$O(N^{-2})$となる。一方、$N/2$-query parity attack with advantage $1/2$は、我々のバウンダリが定数アドバンテージクエリしきい値に達することを示している。さらに、二進ベクトル空間上の置換の和の2つの変種について研究する。まず、トランケーションを含む任意のサージェクティブ線形後処理を許容し、出力サイズ依存を保持する古典的および量子的境界を得る。次に、Dinurの可変出力単一置換構成、$\mathsf{LXoP}$を固定出力幅毎に解析し、古典的および量子的セキュリティ境界を導出する。

論文の概要: Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security

関連論文リスト