Related papers: A note on the differential spectrum of the Ness-Helleseth function

A note on the differential spectrum of the Ness-Helleseth function

URL: http://arxiv.org/abs/2409.03189v1
Date: Thu, 5 Sep 2024 02:28:17 GMT
Title: A note on the differential spectrum of the Ness-Helleseth function
Authors: Ketong Ren, Maosheng Xiong, Haode Yan,
Abstract summary: We study differential equations arising from the Ness-Helleseth function $f_u$ more carefully. We express the differential spectrum of $f_u$ for such $u$ in terms of two quadratic character sums.
Score: 9.776869981132844
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Let $n\geqslant3$ be an odd integer and $u$ an element in the finite field $\gf_{3^n}$. The Ness-Helleseth function is the binomial $f_u(x)=ux^{d_1}+x^{d_2}$ over $\gf_{3^n}$, where $d_1=\frac{3^n-1}{2}-1$ and $d_2=3^n-2$. In 2007, Ness and Helleseth showed that $f_u$ is an APN function when $\chi(u+1)=\chi(u-1)=\chi(u)$, is differentially $3$-uniform when $\chi(u+1)=\chi(u-1)\neq\chi(u)$, and has differential uniformity at most 4 if $ \chi(u+1)\neq\chi(u-1)$ and $u\notin\gf_3$. Here $\chi(\cdot)$ denotes the quadratic character on $\gf_{3^n}$. Recently, Xia et al. determined the differential uniformity of $f_u$ for all $u$ and computed the differential spectrum of $f_u$ for $u$ satisfying $\chi(u+1)=\chi(u-1)$ or $u\in\gf_3$. The remaining problem is the differential spectrum of $f_u$ with $\chi(u+1)\neq\chi(u-1)$ and $u\notin\gf_3$. In this paper, we fill in the gap. By studying differential equations arising from the Ness-Helleseth function $f_u$ more carefully, we express the differential spectrum of $f_u$ for such $u$ in terms of two quadratic character sums. This complements the previous work of Xia et al.

Related papers

PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
We introduce $mathsfPREM$ (Private Relative Error Multiplicative weight update), a new framework for generating synthetic data that a relative error guarantee for statistical queries under $(varepsilon, delta)$ differential privacy (DP) We complement our algorithm with nearly matching lower bounds.
arXiv Detail & Related papers (2025-02-20T18:32:02Z)
A note on the differential spectrum of a class of locally APN functions [1.8109081066789852]
We first give some properties of the differential spectrum of any cryptographic function. By solving some systems of equations over finite fields, we express the differential spectrum of $f_pm1$ in terms of the quadratic character sums.
arXiv Detail & Related papers (2025-01-08T02:17:06Z)
LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
arXiv Detail & Related papers (2024-10-07T19:47:13Z)
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)
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)
Rationality of Four-Valued Families of Weil Sums of Binomials [6.752538702870792]
Weil sums of binomials of the form $WK,s_u=sum_x in K psi(xs - u x)$ are investigated. We show that if the Weil spectrum contains precisely four distinct values, then they must all be rational integers.
arXiv Detail & Related papers (2023-06-26T04:32:48Z)
The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
arXiv Detail & Related papers (2022-09-04T10:01:39Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
arXiv Detail & Related papers (2022-02-10T16:10:41Z)
Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
arXiv Detail & Related papers (2021-09-21T13:19:04Z)
On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
We give an algorithm for this task that achieves an expected $ell_infty$ error bound of $O(frac1epsilonsqrtk log frac1delta)$. On the other hand, the algorithm of Dagan and Kur has a remarkable advantage that the $ell_infty$ error bound of $O(frac1epsilonsqrtk log frac1delta)$ holds not only in expectation but always.
arXiv Detail & Related papers (2020-12-16T17:58:45Z)
Learning and Testing Variable Partitions [13.575794982844222]
We show that $mathcalO(k n2)(delta + epsilon)$ can be learned in time $tildemathcalO(n2 mathrmpoly (1/epsilon)$ for any $epsilon > 0$. We also show that even two-sided testers require $Omega(n)$ queries when $k = 2$.
arXiv Detail & Related papers (2020-03-29T10:12:32Z)

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