On the second-order zero differential properties of several classes of power functions over finite fields
- URL: http://arxiv.org/abs/2409.11693v2
- Date: Thu, 19 Sep 2024 03:19:19 GMT
- Title: On the second-order zero differential properties of several classes of power functions over finite fields
- Authors: Huan Zhou, Xiaoni Du, Xingbin Qiao, Wenping Yuan,
- Abstract summary: Feistel Boomerang Connectivity Table (FBCT) is an important cryptanalytic technique on analysing the resistance of the Feistel network-based ciphers to power attacks such as differential and boomerang attacks.
In this paper, by computing the number of solutions of specific equations over finite fields, we determine explicitly the second-order zero differential spectra of power functions $x2m+3$ and $x2m+5$.
The computation of these entries and the cardinalities in each table aimed to facilitate the analysis of differential and boomerang cryptanalysis of S-boxes.
- Score: 4.100056500795057
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Feistel Boomerang Connectivity Table (FBCT) is an important cryptanalytic technique on analysing the resistance of the Feistel network-based ciphers to power attacks such as differential and boomerang attacks. Moreover, the coefficients of FBCT are closely related to the second-order zero differential spectra of the function $F(x)$ over the finite fields with even characteristic and the Feistel boomerang uniformity is the second-order zero differential uniformity of $F(x)$. In this paper, by computing the number of solutions of specific equations over finite fields, we determine explicitly the second-order zero differential spectra of power functions $x^{2^m+3}$ and $x^{2^m+5}$ with $m>2$ being a positive integer over finite field with even characteristic, and $x^{p^k+1}$ with integer $k\geq1$ over finite field with odd characteristic $p$. It is worth noting that $x^{2^m+3}$ is a permutation over $\mathbb{F}_{2^n}$ and only when $m$ is odd, $x^{2^m+5}$ is a permutation over $\mathbb{F}_{2^n}$, where integer $n=2m$. As a byproduct, we find $F(x)=x^4$ is a PN and second-order zero differentially $0$-uniform function over $\mathbb{F}_{3^n}$ with odd $n$. The computation of these entries and the cardinalities in each table aimed to facilitate the analysis of differential and boomerang cryptanalysis of S-boxes when studying distinguishers and trails.
Related papers
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$.
As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
arXiv Detail & Related papers (2024-10-26T06:21:42Z) - The Differential and Boomerang Properties of a Class of Binomials [28.489574654566677]
We study the differential and boomerang properties of the function $F_2,u(x)=x2big (1+ueta(x)big)$ over $mathbbF_q$.
We disproving a conjecture proposed in citebudaghyan2024arithmetization which states that there exist infinitely many $q$ and $u$ such that $F_2,u$ is an APN function.
arXiv Detail & Related papers (2024-09-21T23:33:00Z) - Further Investigation on Differential Properties of the Generalized Ness-Helleseth Function [13.67029767623542]
The function defined by $f_u(x)=uxd_1+xd_2$ is called the generalized Ness-Helleseth function over $mathbbF_pn$.
For each $u$ satisfying $chi(u+1) = chi(u-1)$, the differential spectrum of $f_u(x)$ is investigated.
arXiv Detail & Related papers (2024-08-30T13:18:23Z) - Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
We study classes of constant-depth circuits with bounds that compute restricted threshold functions.
For large enough values of $mathsfbPTFC0[k]$, $mathsfbPTFC0[k] contains $mathsfTC0[k].
arXiv Detail & Related papers (2024-08-29T09:40:55Z) - On the differential and Walsh spectra of $x^{2q+1}$ over $\mathbb{F}_{q^2}$ [28.489574654566677]
We determine the differential spectrum of the power function $F(x)=x2q+1$ over $mathbbF_q2$.
When the characteristic of $mathbbF_q2$ is $3$, we also determine the value distribution of the Walsh spectrum of $F$.
arXiv Detail & Related papers (2024-07-08T14:01:06Z) - Provably learning a multi-head attention layer [55.2904547651831]
Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models.
In this work, we initiate the study of provably learning a multi-head attention layer from random examples.
We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
arXiv Detail & Related papers (2024-02-06T15:39:09Z) - The SUSY partners of the QES sextic potential revisited [0.0]
We study the SUSY partner Hamiltonians of the quasi- solvable (QES) sextic potential $Vrm qes(x) = nu, x6 + 2, nu, mu,x4 + left[mu2-(4N+3)nu right], x2$, $N in mathbbZ+$.
arXiv Detail & Related papers (2023-11-10T18:38:02Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously.
Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples.
We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
arXiv Detail & Related papers (2023-09-25T17:54:19Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem.
The goal is to approximate $mathbfA$ as a product of low-rank factors.
Our techniques generalize to other common variants of the BMF problem.
arXiv Detail & Related papers (2023-06-02T18:55:27Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations.
The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
arXiv Detail & Related papers (2022-06-17T17:55:43Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$.
We propose a novel random technique, called Ternary Random Feature (TRF)
The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
arXiv Detail & Related papers (2021-10-05T09:33:49Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.