論文の概要: Testing CCZ-equivalence to permutations via projections of Walsh zero spaces, with applications to APN functions
- arxiv url: http://arxiv.org/abs/2611.10269v1
- Date: Fri, 06 Nov 2026 22:06:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-11 09:45:37.631731
- Title: Testing CCZ-equivalence to permutations via projections of Walsh zero spaces, with applications to APN functions
- Title(参考訳): ウォルシュ零空間の射影による置換に対するCCZ等価性のテストとAPN関数への応用
- Abstract要約: ウォルシュが予想を支持する関数について、すべての二次函数を含むアフィンを正確にテストする。
次に、関数 $x3+a-1mathrmTr(a3x9)$ について調べる。
- 参考スコア(独自算出の注目度): 0.152292571922932
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Whether almost perfect nonlinear (APN) permutations exist in even dimension $n\ge 8$ is a long-standing open question, the big APN problem. The only example known in even dimension, on six bits, was found from a quadratic APN function that is not itself a permutation, by Carlet--Charpin--Zinoviev (CCZ) equivalence. It is therefore natural to test APN functions for CCZ-equivalence to a permutation. This amounts to finding two complementary $n$-dimensional subspaces among the zeros of the Walsh transform, which lie in $\mathbb{F}_2^{2n}$. A known necessary condition only uses their projections to $\mathbb{F}_2^n$ and cannot decide every case. We give an exact test for functions whose Walsh supports are affine, including all quadratic functions. It reconstructs the subspaces from their projections, through searches for subspaces of $\mathbb{F}_2^n$ and for constrained bilinear maps. On the benchmarked functions in dimension twelve, it lists them $39$ to $55$ times faster than the generic search of the commonly used sboxU library. We then study the functions $x^3+a^{-1}\mathrm{Tr}(a^3x^9)$, which Göloğlu and Pavlů proved not to be CCZ-equivalent to permutations when $4$ divides $n$. With their result, our computations show that this holds for every even $n\le 24$. In dimension $18$ the necessary condition is satisfied, and the new test decides the case. We conjecture this for every even dimension. We also compile $25$ classes of quadratic APN functions in dimension ten from published instances, with equivalence certificates. No function in these classes or in their switching closure is CCZ-equivalent to a permutation. All code and data are public.
- Abstract(参考訳): ほぼ完全非線形 (APN) な置換が偶数次元$n\ge 8$ に存在するかどうかは、長い間疑問視されてきたが、大きなAPN問題である。
偶数次元で知られている唯一の例は、6ビットで、Carlet--Charpin--Zinoviev (CCZ) 同値性によって、それ自体が置換ではない二次APN函数から発見された。
したがって、置換に対するCCZ等価性のAPN関数をテストすることは自然である。
これはウォルシュ変換の零点の中の2つの相補的な$n$-次元部分空間を見つけ、これは$\mathbb{F}_2^{2n}$にある。
既知の必要条件は、$\mathbb{F}_2^n$への射影のみを使用し、すべてのケースを決定できない。
ウォルシュがサポートしている函数は、すべての二次函数を含むアフィンである。
射影から部分空間を再構成し、$\mathbb{F}_2^n$ の部分空間と制約付き双線型写像を探索する。
12次元のベンチマーク関数では、一般的に使用されるsboxUライブラリの一般的な検索よりも、39ドルから5,5500ドル高速にリストされている。
次に、函数 $x^3+a^{-1}\mathrm{Tr}(a^3x^9)$ について調べるが、これはゲーロールとパヴローが 4$$$$n$ を割り切るとき、置換に同値でないことを証明した。
その結果、我々の計算は、この値が$n\le 24$のすべてに当てはまることを示した。
次元が18ドルになると、必要な条件が満たされ、新しいテストがケースを決定する。
我々はこれをすべての偶数次元に対して予想する。
また、公開インスタンスから10次元の二次APN関数の25ドルクラスを同値証明付きでコンパイルする。
これらのクラスやそれらのスイッチングクロージャの関数は、置換に等価なCCZではない。
すべてのコードとデータは公開されています。
関連論文リスト
- Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space [7.327645708857432]
任意の整数 $pge2$ に対して、厳密な $ell_p$CVP から正則境界への階数保存的還元を与える。
すべての固定整数$pge3$に対して、同じ還元は任意の有理目標に対する正確な$ell_p$アルゴリズムをもたらす。
論文 参考訳(メタデータ) (2026-11-05T01:59:14Z) - Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。
学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。
定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
論文 参考訳(メタデータ) (2026-09-30T18:26:29Z) - Dimension Rigidity and Projective Geometry of Trace-Product Switchings of the Gold Cube [20.271194684947282]
任意の偶次元において、ゴールド準完全非線形関数 $xmapsto x3$ の自然なスカラートレース積スイッチングを分類する。
すべての$ngeq10$に対して、非ゼロ係数は許容されない。
また、正規化階数 2 を 8 次元で $mathbbP1(mathbbF_4)$ で分類する。
論文 参考訳(メタデータ) (2026-08-04T22:36:09Z) - Infinite families of APN permutations in constrained trivariate classes over $\mathbb{F}_{2^m}$ [2.771610203951056]
我々は、Li-KaleyskiのAPN置換ファミリーを2つ拡張する。
特に、$q=2$と$7nmid m$のとき、すべての良い$aneq 1$は、Li-カリースキーと同値なAPN置換CCZを与える。
論文 参考訳(メタデータ) (2026-03-16T11:41:24Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳(メタデータ) (2024-10-26T06:21:42Z) - SIC-POVMs and orders of real quadratic fields [0.0]
低次元のワイル・ハイゼンベルクSICの構造と分類に関する既知のデータを示す。
我々は、SICのガロア倍数は、オーバーオーダーの$mathcalO_Delta$と1対1で対応していると推測する。
我々は、Appleby, Flammia, McConnell, Yard の類体仮説を洗練し、a を定義する等角線に対するベクトルエントリの比によって生成される$mathbbQ(sqrt(d+1)(d-3))$ 上の正確な類体を予測する。
論文 参考訳(メタデータ) (2024-07-10T21:05:23Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳(メタデータ) (2023-01-04T04:15:40Z) - Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。
偏光理論への我々の結果の即時適用について述べる。
論文 参考訳(メタデータ) (2022-05-30T18:01:34Z) - 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) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳(メタデータ) (2020-12-14T18:14:08Z) - Invariant subspaces of two-qubit quantum gates and their application in
the verification of quantum computers [0.0]
我々は、$CP$、$CNOT$および$SWAPalpha$(SWAPのパワー)量子ゲート演算が$n$量子ビットに作用する群について検討する。
各群の作用の下で、$n-$qubit ヒルベルト空間の不変部分空間を決定することができる。
論文 参考訳(メタデータ) (2020-09-08T11:22:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。