Related papers: The Explicit values of the UBCT, the LBCT and the DBCT of the inverse function

The Explicit values of the UBCT, the LBCT and the DBCT of the inverse function

URL: http://arxiv.org/abs/2404.12208v1
Date: Thu, 18 Apr 2024 14:13:40 GMT
Title: The Explicit values of the UBCT, the LBCT and the DBCT of the inverse function
Authors: Yuying Man, Nian Li, Zhen Liu, Xiangyong Zeng,
Abstract summary: This paper further investigates the properties of the inverse function $F(x)=x2n-2$ over $gf_2n$ for arbitrary $n$. Our in-depth analysis of the DBCT of $F(x)$ contributes to a better evaluation of the S-box's resistance against boomerang attacks.
Score: 13.247024319584103
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Substitution boxes (S-boxes) play a significant role in ensuring the resistance of block ciphers against various attacks. The Upper Boomerang Connectivity Table (UBCT), the Lower Boomerang Connectivity Table (LBCT) and the Double Boomerang Connectivity Table (DBCT) of a given S-box are crucial tools to analyze its security concerning specific attacks. However, there are currently no related results for this research. The inverse function is crucial for constructing S-boxes of block ciphers with good cryptographic properties in symmetric cryptography. Therefore, extensive research has been conducted on the inverse function, exploring various properties related to standard attacks. Thanks to the recent advancements in boomerang cryptanalysis, particularly the introduction of concepts such as UBCT, LBCT, and DBCT, this paper aims to further investigate the properties of the inverse function $F(x)=x^{2^n-2}$ over $\gf_{2^n}$ for arbitrary $n$. As a consequence, by carrying out certain finer manipulations of solving specific equations over $\gf_{2^n}$, we give all entries of the UBCT, LBCT of $F(x)$ over $\gf_{2^n}$ for arbitrary $n$. Besides, based on the results of the UBCT and LBCT for the inverse function, we determine that $F(x)$ is hard when $n$ is odd. Furthermore, we completely compute all entries of the DBCT of $F(x)$ over $\gf_{2^n}$ for arbitrary $n$. Additionally, we provide the precise number of elements with a given entry by means of the values of some Kloosterman sums. Further, we determine the double boomerang uniformity of $F(x)$ over $\gf_{2^n}$ for arbitrary $n$. Our in-depth analysis of the DBCT of $F(x)$ contributes to a better evaluation of the S-box's resistance against boomerang attacks.

Related papers

Extended c-differential distinguishers of full 9 and reduced-round Kuznyechik cipher [3.3311266423308252]
This paper introduces em truncated inner $c$-differential cryptanalysis, a novel technique that for the first time enables the practical application of $c$-differential uniformity to block ciphers.<n>Our main contribution is a comprehensive multi-faceted statistical-computational framework, implementing truncated $c$-differential analysis against the full 9-round Kuznyechik cipher.
arXiv Detail & Related papers (2025-07-02T22:27:33Z)
Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
arXiv Detail & Related papers (2025-02-09T22:14:45Z)
Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
We show that the rank of a function $f$ corresponds to the minimum number of Chain of Thought steps required by a single-layer transformer decoder.<n>We also analyze the problem of identifying the position of the $k$-th occurrence of 1 in a Boolean sequence, proving that it requires $k$ CoT steps.
arXiv Detail & Related papers (2025-01-22T16:30:58Z)
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)
On the second-order zero differential properties of several classes of power functions over finite fields [4.100056500795057]
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.
arXiv Detail & Related papers (2024-09-18T04:27:03Z)
Stochastic Bandits Robust to Adversarial Attacks [33.278131584647745]
This paper investigates multi-armed bandit algorithms that are robust to adversarial attacks. We study two cases of this model, with or without the knowledge of an attack budget $C$. We devise two types of algorithms with regret bounds having additive or multiplicative $C$ dependence terms.
arXiv Detail & Related papers (2024-08-16T17:41:35Z)
An in-depth study of the power function $x^{q+2}$ over the finite field $\mathbb{F}_{q^2}$: the differential, boomerang, and Walsh spectra, with an application to coding theory [28.489574654566677]
We examine the finite field $mathbbF_q2$, which consists of $q2$ elements. We first present an alternative method to determine the differential spectrum of the power function $f(x) = xq+2$ on $mathbbF_q2$, incorporating several key simplifications.
arXiv Detail & Related papers (2024-07-08T14:01:06Z)
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)
Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
Ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
arXiv Detail & Related papers (2023-02-27T16:34:21Z)
Phase Transitions in the Detection of Correlated Databases [12.010807505655238]
We study the problem of detecting the correlation between two Gaussian databases $mathsfXinmathbbRntimes d$ and $mathsfYntimes d$, each composed of $n$ users with $d$ features. This problem is relevant in the analysis of social media, computational biology, etc.
arXiv Detail & Related papers (2023-02-07T10:39:44Z)
Near-optimal fitting of ellipsoids to random points [68.12685213894112]
A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
arXiv Detail & Related papers (2022-08-19T18:00:34Z)
Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
arXiv Detail & Related papers (2022-08-12T15:05:07Z)
Provable Robustness of Adversarial Training for Learning Halfspaces with Noise [95.84614821570283]
We analyze the properties of adversarial learning adversarially robust halfspaces in the presence of label noise. To the best of our knowledge, this is the first work to show that adversarial training prov yields classifiers in noise.
arXiv Detail & Related papers (2021-04-19T16:35:38Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.