1 Introduction
We assume that the reader is familiar with basic facts on finite fields. Lidl et al. [13] is a good reference. The finite field with pn elements is denoted by \(\mathbb {F}_{n}\). The cyclic group of invertible elements is denoted by \(\mathbb {F}_{n}^{\times }\) and a generator ω of this group is called a primitive element. Throughout this paper p denotes an odd prime.
Definition 1.1
Let f be a mapping \(f:\mathbb {F}_{n} \rightarrow \mathbb {F}_{n}\).
1.
For \(c\in \mathbb {F}_{n}\) the Δ-mapping of f with respect to c is defined as
$$ {\Delta}_{{f},{c}} (x):=f(x+c)-f(x). $$
2.
Nf(c,a) is defined as \(\#{\Delta }^{-1}_{f,c}(a)\) for \(a,c\in \mathbb {F}_{n}\), i.e. the number of solutions of f(x + c) − f(x) − a = 0.
3.
The family \(\left (N_{f}(c.a)\right )_{c,a\in \mathbb {F}_{n}}\) is called the difference spectrum.
4.
We say that two mappings f and g have the same difference properties if the difference spectrum is equal up to a permutation, i.e. for all \(a,c\in \mathbb {F}_{n}\) there exist \(b,d\in \mathbb {F}_{n}\) with Nf(c,a) = Ng(d,b) and vice versa.
5.
The (differential) uniformity of f is \(\mathcal {U}_{f}:=\max \limits \{N_{f}(c,a)\vert a,c\in \mathbb {F}_{n}, c\neq 0\}\).
6.
A mapping f is called (differentially) k-uniform if \(\mathcal {U}_{f}=k\).
7.
If f is a power mapping xd we will use the notation Δd,c(x),Nd(c,a) and \(\mathcal {U}_{d}\).
Anzeige
Remark 1.1
If k = 1, then f is called perfect nonlinear (PN) or planar. It is well-known that such functions exist only over finite field of odd characteristic. For an example see e.g. [4]. If k = 2, then f is called almost perfect nonlinear (APN). This is the best that can be achieved for even characteristic (see e.g. [7]).
When classifying mappings according to the above properties it is common to focus on the difference properties. The following equivalence relation from [2] is the most common and general known equivalence relation preserving the difference properties of two functions f and g.
Definition 1.2
Two mappings f,g from \(\mathbb {F}_{n}\) to itself are called Carlet-Charpin-Zinoviev-equivalent (CCZ-equivalent) if for some affine permutation \({\mathscr{L}}\) of \(\mathbb {F}_{n}^{2}\) the graph \({\mathscr{L}}({\Gamma }_{f})\) is equal to Γh, where the graph is defined as \({\Gamma }_{M}:=\{(x,f(x))\vert x\in \mathbb {F}_{n}\}\) for a mapping M.
For power mappings we have the following simplification by Dempwolff [5].
Anzeige
Theorem 1.3
Let \(\mathbb {F}_{n}\) be a finite field of characteristic p and xk and xl be power functions on \(\mathbb {F}_{n}\). Then xk and xl are CCZ-equivalent, if and only if there exists a positive integer 0 ≤ m < n, such that l = pmk mod (pn − 1) or kl = pm mod (pn − 1).
Remark 1.2
It is well-known that a power mapping xd is a permutation over \(\mathbb {F}_{n}\) iff gcd(d,pn − 1) = 1. The inverse is given by \(x^{d^{-1}}\), where d− 1 is s.t. d− 1 ⋅ d = 1 mod pn − 1. Note, that the latter condition in the above theorem means that \(x^{p^{n-m}k}\) and xl are inverse to each other. Moreover the theorem states that if xd is a permutation with inverse \(x^{d^{-1}}\) then these mappings have the same difference properties.
The following lemma is well-known (see e.g. [7])
Lemma 1.4
For a power mapping xd over \(\mathbb {F}_{n}\) the difference spectrum is completely determined by considering \({\Delta }_{d,1}\left (x-\frac {1}{2}\right )=a,a\in \mathbb {F}_{n}\).
Classifying mappings of low uniformity up to CCZ-equivalence is of interest in cryptography since differential and linear cryptanalysis exploit weaknesses of the uniformity of the functions which are used in AES and many other block ciphers. Helleseth, Rong and Sandberg conducted extensive computer search in the 90s to classify k-uniform power mappings. These numerical results are well-known as the Helleseth-Rong-Sandberg tables (H-R-S tables). Several inifinite families of mappings have been discovered since then and their uniformity determined in a series of papers thereby explaining some of these entries (see e.g. [7, 9, 10, 14, 15]).
For applications in cryptography, one would like to employ mappings f for which \(\mathcal {U}_{f}\) is as small as possible. The proprietary hash function Curl employed in the cryptocurrency IOTA for example makes use of ternary S-Boxes and is vulnerable to differential cryptanalysis. After being broken the IOTA foundation developed in cooporation with Cybercrypt the ternary hash function Troika as its substitute and initiated a crypto challenge over 200.000 €. As the foundation is currently developing new computer chips built around base-3 logic, mappings with low uniformity over \(\mathbb {F}_{3^{n}}\) have become cryptographically relevant (see [11]). In this context research on bijective power mappings with low uniformity over \(\mathbb {F}_{n}\) and \(\mathbb {F}_{3^{n}}\) in particular is of interest as they can be also employed in SPN- or stream ciphers. As mentioned before planar functions have the lowest possible uniformity of one and therefore cannot be bijective. Thus bijective mappings have necessarily a uniformity of at least two. That these can be still cryptograhically strong is well demonstrated for characteristic 2 by the block cipher AES.
1.1 Our contribution
In this paper we contribute to this development and give a family of power mappings \(x^{d_{n}}\) with low uniformity over \(\mathbb {F}_{n}\), which is bijective for p ≡ 3 mod 4 and n odd. In case of p = 3 we get a bijective family \(x^{d_{n}}\) of uniformity \(\mathcal {U}_{d_{n}}\leq 4,\) where the family \(x^{d^{-1}_{n}}\) of inverses has a very simple description and is thus of particular interest for this new direction in cryptography. As a side result we will get that the mapping \(x^{d_{n}},d_{n}=\frac {p^{n}-1}{2}+2\) is bijective for p ≡ 3 mod 4 and n odd. Its uniformity was computed in [10].
1.2 Organization
This paper is organized as follows. In the next section we will introduce our results. Then we will give the mathematical background required for the proofs. In Section 4 we will introduce the multivariate method from [8] and compute the uniformity as well as the bijectivity in several subsections. In the final section we will discuss further research.
2 New power mappings of low uniformity
In this paper, we prove the following theorems.
Theorem 2.1
Let \(x^{d_{n}}, d_{n}=\frac {p^{n}-1}{2}+p^{\frac {n+1}{2}}+1\) be a power function from \(\mathbb {F}_{n}\) to \(\mathbb {F}_{n}\), p≠ 3 an odd prime and n odd. Then
1.
\(x^{d_{n}}\) is a permutation for p ≡ 3 mod 4.
2.
\(\mathcal {U}_{d_{n}}=3,\) if p ≡ 1 mod 4 and either p≠ 17 or n > 1,
3.
\(\mathcal {U}_{d_{n}}=2\), if p = 17 and n = 1,
4.
\(\mathcal {U}_{d_{n}}\in \{4,6\}\) otherwise.
Remark 2.1
Since \(\frac {p^{n}-1}{2}\) is even for p ≡ 1 mod 4 the exponent dn is even and thus \(x^{d_{n}}=(-x)^{d_{n}}\). Therefore \(x^{d_{n}}\) cannot be a permutation in this case.
For p = 3 we have
Theorem 2.2
The family \(x^{d_{n}}, d_{n}=\frac {3^{n}-1}{2}+3^{\frac {n+1}{2}}+1\) is bijective with inverse \(x^{d^{\prime }_{n}},\) where
and \(\mathcal {U}_{d_{n}}=\mathcal {U}_{d^{\prime }_{n}}\in \{3,4\}\) for n > 1.
$$d^{\prime}_{n}=\left\lbrace\begin{array}{l}\frac{3^{\frac{n+1}{2}}-1}{2}, n\equiv 1\bmod 4\\ \frac{3^{n}-1}{2}+\frac{3^{\frac{n+1}{2}}-1}{2}, n\equiv 3\bmod 4 \end{array}\right.$$
It is \(\mathcal {U}_{d_{n}}=3\) for n = 1.
The uniformity for p = 5 in theorem 2.1 and for the family in theorem 2.2 was already proven in [8], whereas the explicit and simple description of the family of inverses in theorem 2.2 is new. Note that swapping n ≡ 1 mod 4 and n ≡ 3 mod 4 in the definition of \(d^{\prime }_{n}\) gives the mapping introduced in [7] proven to be APN in [14]. This mapping is no longer bijective. Statement 4 of theorem 2.1 cannot be narrowed in general and this theorem explains the following open entries in the H-R-S tables as Table 1 shows.
Table 1
Open cases
p | n | d | uniformity | H-R-S entry |
|---|---|---|---|---|
7 | 1 | 5 | 4 | no H-R-S table |
7 | 3 | 179 | 4 | open H-R-S entry |
7 | 5 | 8453 | 6 | no H-R-S table |
7 | 7 | 412115 | 6 | no H-R-S table |
11 | 1 | 7 | 2 | no H-R-S table |
11 | 3 | 677 | 4 | open H-R-S entry |
11 | 5 | 80647 | 6 | no H-R-S table |
d in Table 1 is the cyclotomic cosetleader defined as
As this family explains open entries in the H-R-S table it is not CCZ-equivalent to known ones. It can also be seen as a generalization for odd n of the family \(x^{d_{n}},d_{n}=\frac {p^{n}-1}{2}+2\) treated in [10]. Therefore it is not surprising that we will also prove the following theorem
$$\min\left( \{d\cdot p^{i} \bmod (p^{n}-1)\vert 0\leq i \leq n-1\}\right).$$
Theorem 2.3
The family of power mappings \(x^{d_{n}},d_{n}=\frac {p^{n}-1}{2}+2\) is bijective for p ≡ 3 mod 4 and n odd.
It was shown in [10] that its uniformity is 4.
In [8] it was shown that the family from theorem 2.2 is not CCZ-equivalent to known ones.
3 Preliminaries
The univariate polynomial ring over a finite field is denoted by \(\mathbb {F}_{n}[x]\). The polynomial ring in two variables x,y over \(\mathbb {F}_{n}\) is denoted by \(\mathbb {F}_{n} [x,y]\). We will need the following facts about quadratic characters. A detailed treatment on the theory of characters can be found in [12] or [13].
The quadratic character over \(\mathbb {F}_{n}\) is the mapping \(\chi _{p^{n}}:\mathbb {F}_{n}\rightarrow \{-1,0,1\}\subset \mathbb {C}\) which can be by common abuse of language represented by the power mapping \(\chi _{p^{n}}(x)=x^{\frac {p^{n}-1}{2}}\). This mapping has the following properties
The following two propositions play a central role in this paper.
$$\chi_{p^{n}}(\alpha)=\left\{\begin{array}{rl} 0,&\text{ if }\alpha=0,\\ 1,&\text{ iff }x^{2}-\alpha=0\text{ has a solution in }\mathbb{F}_{n}^{\times},\\ -1&\text{ otherwise.} \end{array}\right. $$
Proposition 3.1
1.
We have \(\chi _{p^{n}}(-1)=1\) iff \(\frac {p^{n}-1}{2}\) is even.
2.
If n is odd then \(\chi _{p^{n}}(-1)=1\) iff p ≡ 1 mod 4.
3.
\(\chi _{p^{n}}(a\cdot b)=\chi _{p^{n}}(a)\chi _{p^{n}}(b)\) for all \(a,b\in \mathbb {F}_{n}\).
If p is clear from the context we will just write χn.
Proposition 3.2
If the equation \(x^{p-1}=a,a\in \mathbb {F}_{n}^{\times }\) has a p − 1-th root α over \(\mathbb {F}_{n}\) then it has exactly p − 1 roots. These are given by \(\omega ^{i}\alpha , i=0,\dots ,p-2,\) ω a primitive element of \(\mathbb {F}_{p^{\times }}\).
Proof
As a≠ 0 the same is true for the solution α. Obviously \(\omega ^{i}\alpha ,i=0,\dots ,p-2\) are p − 1 pairwise different solutions of xp− 1 = a or xp− 1 − a = 0 respectively. As a polynomial of degree p − 1 has at most p − 1 zeros the assertion follows. □
The Weil estimate (see [13], p. 225, [1], p. 183) on character sums given in the next theorem is particularly useful to prove that certain character sums are non-zero, which are often encountered when computing the uniformity of power mappings.
Theorem 3.3
Let \(f(x)\in \mathbb {F}_{n}[x]\) be a polynomial with m distinct zeros in its splitting field, which is not a square of another polynomial, then
If f(x) has degree 2 it is
$$ \left\vert\sum\limits_{\alpha\in\mathbb{F}_{n}}\chi_{n}(f(\alpha))\right\vert\leq (m-1)\sqrt{p^{n}}.$$
$$ \left\vert\sum\limits_{\alpha\in\mathbb{F}_{n}}\chi_{n}(f(\alpha))\right\vert\leq 1.$$
With Trn we denote the trace function from \(\mathbb {F}_{n}\) onto \(\mathbb {F}_{p}\), which is given by
The trace is linear and its kernel, which will be of interest here, has been parametrized by Hilbert in its famous theorem Hilbert 90 which is given below.
$$Tr_{n}(x)=x^{p^{n-1}}+\dots+x^{p}+x.$$
Theorem 3.4
It is Trn(γ) = 0 iff \(\gamma =\alpha ^{p}-\alpha , \alpha \in \mathbb {F}_{n}\).
Remark 3.1
Note that the mapping xp − x is p −to − 1 over \(\mathbb {F}_{n}\), because it is linear with kernel \(\mathbb {F}_{p}\).
The proof based on the multivariate method requires to determine the zeros of multivariate equations in two unknowns which explains its name. Systematic methods for solving such equations are given in e.g. classical elimination theory. An important algebraic tool in this theory is the well-known resultant of f(x,y) and \(g(x,y),f,g\in \mathbb {F}_{n}[x,y]\) with respect to y, which we denote by res(f,g,y). We will make use of the next proposition which states how the resultant can be used for determining the solutions of a system of polynomial equations.
Proposition 3.5
Given \(f(x,y),g(x,y)\in \mathbb {F}_{n}[x,y]\setminus \{0\}\).
1.
res\((f,g,y)\in \mathbb {F}_{n}[x]\).
2.
There are polynomials \(p,q\in \mathbb {F}_{n}[x,y]\) such that
and therefore the system of equations
has a solution (α,β) over a proper field extension only if res(f,g,y)(α) = 0.
$$pf+qg=\text{res}(f,g,y)$$
$$ \begin{array}{lll} f(x,y)&=&0\\ g(x,y)&=&0 \end{array} $$
For further reading on the resultant and elimination theory we refer to [3].
4 The multivariate method: Proof of Theorem 2.1
In this section we prove theorem 2.1 and thereby giving a simple and self-contained introduction to the multivariate method.
4.1 The multivariate representation
Recall that by theorem 1.3 and lemma 1.4 we can restrict to consider
The first step is to express this equation as a system of multivariate equations.
$$ {\Delta}_{d_{n},1}\left( x-\frac{1}{2}\right)=a. $$
To this end we denote the conjugation (Galois automorphism) \(x\mapsto x^{p^{\frac {n+1}{2}}}\) by x∗ and set y := x∗. Then it is
over \(\mathbb {F}_{n}\) and
over \(\mathbb {F}_{p}\). The latter property will be very useful later. Analogously we set a∗ = b.
$$y^{\ast}=x^{p}$$
$$y=x$$
We get
and the Δ-mapping can be represented by
By conjugation of F1 with ∗ we get
as \(\chi _{n}\left (x\pm \frac {1}{2}\right )^{\ast }=\chi _{n}\left (x\pm \frac {1}{2}\right )\).
$$x^{d_{n}}=\chi_{n}(x)yx$$
$$ \begin{array}{@{}rcl@{}} F_{1}: \chi_{n}\left( x+\frac{1}{2}\right)\left( y+\frac{1}{2}\right)\left( x+\frac{1}{2}\right)-\chi_{n}\left( x-\frac{1}{2}\right)\left( y-\frac{1}{2}\right)\left( x-\frac{1}{2}\right)=a. \end{array} $$
(1)
$$ \begin{array}{@{}rcl@{}} F_{2}: \chi_{n}\left( x+\frac{1}{2}\right)\left( y+\frac{1}{2}\right)\left( x^{p}+\frac{1}{2}\right)-\chi_{n}\left( x-\frac{1}{2}\right)\left( y-\frac{1}{2}\right)\left( x^{p}-\frac{1}{2}\right)=b \end{array} $$
(2)
We make a case distinction according to the 4 possible values of \(\chi _{n}(x+\frac {1}{2}),\chi _{n}(x-\frac {1}{2})\) to get the sought for representation.
Case 1:
\(\chi _{n}\left (x-\frac {1}{2}\right )=1, \chi _{n}\left (x+\frac {1}{2}\right )=1\)
$$ \begin{array}{@{}rcl@{}} F_{11}:x+y-a=0\\ F_{12}:x^{p}+y-b=0 \end{array} $$
(3)
Case 2:
\(\chi _{n}\left (x-\frac {1}{2}\right )=-1, \chi _{n}\left (x+\frac {1}{2}\right )=1\)
$$ \begin{array}{@{}rcl@{}} F_{21}: xy-\frac{1}{2}a+\frac{1}{4}=0\\ F_{22}:x^{p}y-\frac{1}{2}b+\frac{1}{4}=0 \end{array} $$
(4)
Case 3:
\(\chi _{n}\left (x-\frac {1}{2}\right )=1, \chi _{n}\left (x+\frac {1}{2}\right )=-1\)
$$ \begin{array}{@{}rcl@{}} F_{31}: xy+\frac{1}{2}a+\frac{1}{4}=0\\ F_{32}:x^{p}y+\frac{1}{2}b+\frac{1}{4}=0 \end{array} $$
(5)
Case 4:
\(\chi _{n}\left (x-\frac {1}{2}\right )=-1, \chi _{n}\left (x+\frac {1}{2}\right )=-1\)
The above case distinction does not capture the cases \(x=\pm \frac {1}{2}\) as \(\chi _{n}\left (\frac {1}{2}-\frac {1}{2}\right )=\chi _{n}\left (-\frac {1}{2}+\frac {1}{2}\right )=0\). We have
and
by proposition 3.1. This gives the exceptional cases a = ± 1. We will see that \(a=\pm \frac {1}{2}\) will lead to exceptional cases as well. These lie all in the base field \(\mathbb {F}_{p}\). From now on we assume \(a\in \mathbb {F}_{n}\setminus \mathbb {F}_{p}\) and treat \(a\in \mathbb {F}_{p}\) in Section 4.4.
$$ \begin{array}{@{}rcl@{}} F_{41}: x+y+a=0\\ F_{42}: x^{p}+y+b=0 \end{array} $$
(6)
$$ \chi_{n}\!\left( \frac{1}{2} + \frac{1}{2}\right)\!\left( \frac{1}{2} + \frac{1}{2}\right)\!\left( \frac{1}{2} + \frac{1}{2}\right) - \chi_{n}\left( \frac{1}{2} - \frac{1}{2}\right)\!\left( \frac{1}{2} - \frac{1}{2}\right)\!\left( \frac{1}{2} - \frac{1}{2}\right) = \chi_{n}(1)\!\cdot\! 1 = 1 $$
(7)
$$ \begin{array}{@{}rcl@{}} \chi_{n}\left( -\frac{1}{2}+\frac{1}{2}\right)\left( -\frac{1}{2}+\frac{1}{2}\right)\left( -\frac{1}{2}+\frac{1}{2}\right)-\\\chi_{n}\left( -\frac{1}{2}-\frac{1}{2}\right)\left( -\frac{1}{2}-\frac{1}{2}\right)\left( -\frac{1}{2}-\frac{1}{2}\right)= -\chi_{n}(-1)=\pm 1. \end{array} $$
(8)
The principle of the multivariate method is now to compute the solutions of \(F_{i1},F_{i2}, i=1,\dots ,4\) with elementary elimination theory. Thereby we are only interested in solutions of the form \(\left (\alpha ,\alpha ^{\ast }\right )\). We call \(F_{i1},F_{i2},i=1,\dots ,4\) fundamental equations and the above solutions suitable in the sequel as exactly these yield solutions of \({\Delta }_{d_{n},1}(x-\frac {1}{2})=a\) when the corresponding character condition is fulfilled. In this case the solution is called an actual solution. It will turn out that identifying suitable solutions for this type of power mappings can be done by uniform techniques and usually gives a tight upper bound on the uniformity. This makes the multivariate method to a powerful universal tool to study the uniformity. The problem of determining if the corresponding character condition is fulfilled for a suitable solution, i.e. if it is an actual solution, is much harder in general. The corresponding underlying mathematical problem to do so is easier described by the notion of a suitable solution as we will see. This explains why we distinguish between these types of solutions (see also Section 5).
One possibility to determine suitable solutions is to compute the resultant res(Fi,1,Fi,2,y) (by abuse of language) of the left hand side of the fundamental equations with respect to y. This can be seen as follows.
By proposition 3.5 the equation \({\Delta }_{d_{n},1}(x-\frac {1}{2})=a\) has a suitable solution α only if α is a zero of one of the above res(Fi,1,Fi,2,y). Then one shows which of the zeros α yield suitable solutions. Moreover as long as we do not encounter an exceptional case for the quadratic character any solution belongs exactly to one of the four cases. Therefore the above resultants are called fundamental polynomials. In general the resultant can be computed very easily with the help of computer algebra systems like
magma.Note that all suitable solutions \(\left (\alpha ,\alpha ^{\ast }\right )\) of Fi1,Fi2, when considered as a system of multivariate equations yield a zero α of the resultant but not the other way around. There might exist zeros α of the resultant which do not extend to solutions of Fi1,Fi2 at all. All other zeros α extend to a solution \(\left (\alpha ,\upbeta \right )\) of Fi1,Fi2 but β is not necessarily equal to α∗. Therefore not all zeros of res(Fi,1,Fi,2,y) yield suitable solutions and not all suitable solutions result in actual solutions. In principle any univariate polynomial ϕi(x) with ϕi(α) = 0 for all actual solutions \(\left (\alpha ,\alpha ^{\ast }\right )\) of Fi1 can be employed in the multivariate method. Therefore we call ϕi(x) a fundamental polynomial in the sequel. Here we compute such a ϕi(x) by hand e.g.
The latter computation is defined as long as \(a\not =\frac {1}{2},\) which we excluded. The exceptional case \(a=-\frac {1}{2}\) comes into play by computing ϕ3 in the same vein. We get
$$\phi_{1}(x)=F_{12}-F_{11}\text{ and }\phi_{2}(x)=\left( \frac{1}{\left( -\frac{1}{2}a+\frac{1}{4}\right)}\left( x^{p-1}\cdot F_{21}-F_{22}\right)\right).$$
Case 1:
\(\chi _{n}\left (x-\frac {1}{2}\right )=1, \chi _{n}\left (x+\frac {1}{2}\right )=1\)
$$ \begin{array}{@{}rcl@{}} \phi_{1}(x):=x^{p} - x + a-b \end{array} $$
(9)
Case 2:
\(\chi _{n}\left (x-\frac {1}{2}\right )=-1, \chi _{n}\left (x+\frac {1}{2}\right )=1\)
$$ \begin{array}{@{}rcl@{}} \phi_{2}(x):=\left( x^{p-1}-\frac{b-\frac{1}{2}}{a-\frac{1}{2}}\right),a\not=\frac{1}{2} \end{array} $$
(10)
Case 3:
\(\chi _{n}\left (x-\frac {1}{2}\right )=1, \chi _{n}\left (x+\frac {1}{2}\right )=-1\)
$$ \begin{array}{@{}rcl@{}} \phi_{3}(x):=\left( x^{p-1} -\frac{b+\frac{1}{2}}{a + \frac{1}{2}}\right),a\not=-\frac{1}{2} \end{array} $$
(11)
Case 4:
\(\chi _{n}\left (x-\frac {1}{2}\right )=-1, \chi _{n}\left (x+\frac {1}{2}\right )=-1\)
$$ \begin{array}{@{}rcl@{}} \phi_{4}(x):=x^{p}-x-a+b \end{array} $$
(12)
4.2 The contribution of ϕ1 and \(\phi _{4}, a\in \mathbb {F}_{n}\setminus \mathbb {F}_{p}\)
By 3.4 and remark 3.1 the fundamental polynomials ϕ1(x),ϕ4(x) split over \(\mathbb {F}_{n}\) as Trn(±(b − a)) = 0 and the zeros of ϕ1 and ϕ4 can be represented as
where ϕ1(α) = 0 and \(\upbeta \in \mathbb {F}_{p}\). We will show that ϕ1 contributes exactly one suitable solution. To do so we prove at first that ϕ1 contributes at most one suitable solution. Assume the contrary. Then there exist \({\upbeta }_{1},{\upbeta }_{2}\in \mathbb {F}_{p}\) with
and
Subtracting both equations gives
As \({\upbeta }_{1}-{\upbeta }_{2}\in \mathbb {F}_{p}\) it is (β1 −β2)∗ = (β1 −β2). Consequently
It follows β1 −β2 = 0 and thus β1 = β2, which contradicts our assumption.
$$\alpha+\upbeta \text{ and }-\left( \alpha+\upbeta\right)\text{ respectively,}$$
$$\alpha+{\upbeta}_{1}+\alpha^{\ast}+{\upbeta}_{1}^{\ast}=a$$
$$\alpha+{\upbeta}_{2}+\alpha^{\ast}+{\upbeta}_{2}^{\ast}=a.$$
$${\upbeta}_{1}-{\upbeta}_{2}+({\upbeta}_{1}-{\upbeta}_{2})^{\ast}=0.$$
$${\upbeta}_{1}-{\upbeta}_{2}+({\upbeta}_{1}-{\upbeta}_{2})^{\ast}=2\cdot ({\upbeta}_{1}-{\upbeta}_{2})=0.$$
Now consider the linear mapping L : x↦x + x∗ over \(\mathbb {F}_{n}\). Any element α in the preimage of \(L^{-1}(a), a\in \mathbb {F}_{p^{n}}\setminus \mathbb {F}_{p}\) yields a suitable solution of x + y = x + x∗ = a and vice versa. It follows that #L− 1(a) ≤ 1. Moreover the mapping is equal to 2x over \(\mathbb {F}_{p}\) as in this case x∗ = x.. Thus the mapping is injective over the whole field \(\mathbb {F}_{n}\) and therefore L is a permutation. From this it follows that ϕ1 contributes exactly one suitable solution (over the whole field \(\mathbb {F}_{n}\)).
A direct consequence is that the fundamental (6) has exactly one suitable solution as well, which is equal to \(-\left (\alpha +\upbeta \right ) \) where α +β denotes the suitable solution of (3). We have
From this it follows together with proposition 3.1 and the fact that the suitable solutions of (3) and (6) differ by a sign:
$$\chi_{n}\left( -x-\frac{1}{2}\right)=\chi_{n}(-1)\chi_{n}\left( x+\frac{1}{2}\right)\text{ and }\chi_{n}\left( -x+\frac{1}{2}\right)=\chi_{n}(-1)\chi_{n}\left( x-\frac{1}{2}\right).$$
1.
If p ≡ 3 mod 4 then for all \(a\in \mathbb {F}_{n}\setminus \mathbb {F}_{p}\) there exists exactly one \(\alpha +{\upbeta }_{0},{\upbeta }_{0}\in \mathbb {F}_{p}\) of ϕ1(x), which yields a suitable solution of the fundamental (3) and the corresponding \(-\left (\alpha +{\upbeta }_{0}\right )\) extends to the only suitable solution of the fundamental (6).
Moreover it is χn(− 1) = − 1 and therefore \(\alpha +{\upbeta }_{0},-\left (\alpha +{\upbeta }_{0}\right )\) yield 2 actual solutions iff \(\chi _{n}(\alpha +{\upbeta }_{0}-\frac {1}{2})=\chi _{n}(\alpha +{\upbeta }_{0}+\frac {1}{2})=1\) and 0 otherwise.
2.
If p ≡ 1 mod 4 then for all \(a\in \mathbb {F}_{n}\setminus \mathbb {F}_{p}\) there exists exactly one zero α + β0 of ϕ1(x), which yields a suitable solution of the fundamental (3) and the corresponding \(-\left (\alpha +{\upbeta }_{0}\right )\) extends to the only suitable solution of the fundamental (6).
Here χn(− 1) = 1 and therefore either α + β0 or \(-\left (\alpha +{\upbeta }_{0}\right ) \) yields to 1 actual solution iff either \(\chi _{n}(\alpha +{\upbeta }_{0}-\frac {1}{2})=\chi _{n}(\alpha +{\upbeta }_{0}+\frac {1}{2})=1\) or \(\chi _{n}(\alpha +{\upbeta }_{0}-\frac {1}{2})=\chi _{n}(\alpha +{\upbeta }_{0}+\frac {1}{2})=-1\) and 0 otherwise.
4.3 The contribution of ϕ2 and \(\phi _{3},a\in \mathbb {F}_{n}\setminus \mathbb {F}_{p}\)
We have that \(p^{\frac {n+1}{2}}-1\) is always divisible by p − 1 which follows directly from the general identity \(p^{l}-1=(p-1){\sum }_{i=0}^{l-1}p^{i},l\in \mathbb {N}\). Therefore for \(a\in \mathbb {F}_{n} \)
is a (p − 1)-th root of \(\frac {b-\frac {1}{2}}{a-\frac {1}{2}}\). By proposition 3.2 ϕ2 splits over \(\mathbb {F}_{n}\) as follows
Analogously we have
Plugging \(\omega ^{i}\left (a-\frac {1}{2}\right )^{\frac {p^{\frac {n+1}{2}}-1}{p-1}}\) into the left hand side of the fundamental (4) and making use of xy = x2 over \(\mathbb {F}_{p}\) gives
$$\left( a-\frac{1}{2}\right)^{\frac{p^{\frac{n+1}{2}}-1}{p-1}}$$
$$ \phi_{2}(x)=\left( x-\omega^{0}\left( a-\frac{1}{2}\right)^{\frac{p^{\frac{n+1}{2}}-1}{p-1}}\right)\cdot\dots\cdot\left( x-\omega^{p-2}\left( a-\frac{1}{2}\right)^{\frac{p^{\frac{n+1}{2}}-1}{p-1}}\right),\omega\in\mathbb{F}_{p}^{\times}. $$
(13)
$$ \phi_{3}(x)=\left( x-\omega^{0}\left( a+\frac{1}{2}\right)^{\frac{p^{\frac{n+1}{2}}-1}{p-1}}\right)\cdot\dots\cdot\left( x-\omega^{p-2}\left( a+\frac{1}{2}\right)^{\frac{p^{\frac{n+1}{2}}-1}{p-1}}\right),\omega\in\mathbb{F}_{p}^{\times}. $$
(14)
$$ \begin{array}{@{}rcl@{}} \omega^{2i}\left( a-\frac{1}{2}\right)^{\frac{p^{\frac{n+1}{2}}-1}{p-1}\cdot\left( p^{\frac{n+1}{2}}+1\right)}=\omega^{2i}\left( a-\frac{1}{2}\right)^{\frac{(p-1)\cdot p^{n}+p^{n}-1}{p-1}}\\=\omega^{2i}\left( a-\frac{1}{2}\right)\left( a-\frac{1}{2}\right)^{\frac{p^{n}-1}{p-1}}=\omega^{2i}\left( a-\frac{1}{2}\right)^{\frac{p^{n}-1}{p-1}}\left( a-\frac{1}{2}\right). \end{array} $$
(15)
Thus fundamental (4) is fulfilled iff \(\omega ^{2i}\left (a-\frac {1}{2}\right )^{\frac {p^{n}-1}{p-1}}=\frac {1}{2}\) i.e.
for a proper chosen 0 ≤ i ≤ p − 2 as by assumption \(\left (a-\frac {1}{2}\right )\not =0\). We have \(\left (\left (a-\frac {1}{2}\right )^{-\frac {p^{n}-1}{p-1}}\right )^{p-1}=1\) and conclude that the right hand side of (16) lies in \(\mathbb {F}_{p}\). Since the quadratic character is a homomorphism with respect to multiplication (see proposition 3.1) and \(\frac {p^{n}-1}{p-1}={\sum }_{j=0}^{n-1}p^{j}\) is odd we get \(\chi _{n}\left (\left (a-\frac {1}{2}\right )^{\frac {p^{n}-1}{p-1}}\right )=\chi _{n}(a-\frac {1}{2})\). Therefore such an i exists iff \(\chi _{n}\left (\frac {1}{2}\left (a-\frac {1}{2}\right )\right )=1\) as ω2i runs through all squares in \(\mathbb {F}_{p}\) for 0 ≤ i ≤ p − 2. Moreover since x2 is 2-to-1 over \(\mathbb {F}_{p}\) (16) has exactly two solutions. These are denoted by \(\pm \omega ^{i_{n}}\). It follows that the possible suitable solutions of the fundamental (4) are
Analogously one shows that the fundamental (5) has two suitable solutions iff \(\chi _{n}\left (-\frac {1}{2}\left (a+\frac {1}{2}\right )\right )=1\). In this case the two suitable solutions of the fundamental (5) are
where \(i_{n}\in \{0,\dots ,p-2\}\) is s.t.
Recall that \(\chi _{n}\left (-x-\frac {1}{2}\right )=\chi _{n}(-1)\chi _{n}\left (x+\frac {1}{2}\right )\) and \(\chi _{n}\left (-x+\frac {1}{2}\right )=\chi _{n}(-1)\chi _{n}\left (x-\frac {1}{2}\right )\). Thus we get in dependence of p mod 4 :
$$ \begin{array}{@{}rcl@{}} \omega^{2i}=\frac{1}{2}\left( a-\frac{1}{2}\right)^{-\frac{p^{n}-1}{p-1}},\end{array} $$
(16)
$$ \begin{array}{@{}rcl@{}} \pm \omega^{i_{n}}\left( a-\frac{1}{2}\right)^{\frac{p^{\frac{n+1}{2}}-1}{p-1}} \end{array} $$
(17)
$$ \begin{array}{@{}rcl@{}} \pm \omega^{i_{n}}\left( a+\frac{1}{2}\right)^{\frac{p^{\frac{n+1}{2}}-1}{p-1}}, \end{array} $$
(18)
$$\omega^{2i_{n}}=\left( -\frac{1}{2}\right)\left( a+\frac{1}{2}\right)^{-\frac{p^{n}-1}{p-1}}.$$
1.
If p ≡ 3 mod 4 then the fundamental (4) has exactly two suitable solutions iff \(\chi _{n}\left (\frac {1}{2}\left (a-\frac {1}{2}\right )\right )=1\).
We have χn(− 1) = − 1 and therefore the suitable solutions yield actual solutions iff additionally the character condition is fulfilled for one and thus both solutions given in (17) and 0 actual solutions otherwise.
2.
If p ≡ 1 mod 4 then the fundamental (4) has two suitable solutions iff \(\chi _{n}\left (\frac {1}{2}\left (a-\frac {1}{2}\right )\right )=1\) as in the other case.
We have χn(− 1) = 1 and therefore at most one of the two suitable solutions given in (17) fulfills the character condition.
4.4 Exceptions \(a\in \mathbb {F}_{p}\)
Over the base field \(\mathbb {F}_{p}\) it is b = a. Applying the multivariate method by taking this into account yields
Case 1:
\(\chi (x-\frac {1}{2})=1, \chi (x+\frac {1}{2})=1\)
$$ \begin{array}{@{}rcl@{}} F_{11}:x+y-a=0 \end{array} $$
(19)
$$ \begin{array}{@{}rcl@{}} F_{12}:x^{p}+y-a=0 \end{array} $$
(20)
Case 2:
\(\chi (x-\frac {1}{2})=-1, \chi (x+\frac {1}{2})=1\)
$$ \begin{array}{@{}rcl@{}} F_{21}: xy-\frac{1}{2}a+\frac{1}{4}=0\\ F_{22}:x^{p}y-\frac{1}{2}a+\frac{1}{4}=0 \end{array} $$
(21)
Case 3:
\(\chi (x-\frac {1}{2})=1, \chi (x+\frac {1}{2})=-1\)
$$ \begin{array}{@{}rcl@{}} F_{31}: xy+\frac{1}{2}a+\frac{1}{4}=0\\ F_{32}:x^{p}y+\frac{1}{2}a+\frac{1}{4}=0 \end{array} $$
(22)
Case 4:
\(\chi \left (x-\frac {1}{2}\right )=-1, \chi \left (x+\frac {1}{2}\right )=-1\)
$$ \begin{array}{@{}rcl@{}} F_{41}:x+y+a=0\\ F_{42}: x^{p}+y+a=0 \end{array} $$
(23)
We get
and
Obviously all zeros of \(\phi _{1},\dots ,\phi _{4}\) lie in \(\mathbb {F}_{p}\). Note that for a = ± 1 we enter the exceptional cases for the character conditions treated in (7) and (8). We conclude that if \(a\in \mathbb {F}_{p}\) then the preimage
Thus we can restrict to consider \(x^{d_{n}}\) over \(\mathbb {F}_{p}\). As \(x^{d_{n}}=\chi _{1}(x)x^{2}\) over \(\mathbb {F}_{p}\) we can apply theorem 3 and the remark on p. 368 of [10], which together state that
over the base fields.
$$ \phi_{1}(x)=\phi_{4}(x)=x^{p}-x, $$
$$ \phi_{2}(x)=x^{p-1}F_{21}-F_{22}=-\frac{1}{2}a+\frac{1}{4}\left( x^{p-1}-1\right) $$
$$ \phi_{3}(x)=x^{p-1}F_{31}-F_{32}=\frac{1}{2}a+\frac{1}{4}\left( x^{p-1}-1\right). $$
$$ {\Delta}_{1,d_{n}}\left( x-\frac{1}{2}\right)^{-1}(a)\subset \mathbb{F}_{p}. $$
$$ \mathcal{U}_{d_{n}}=\left\lbrace\begin{array}{l} 4\text{, if }p\equiv 3\bmod 4\text{ and }p\not=3,\\ 3\text{, if } p\equiv 1 \bmod 4\text{ and either }p\not=17\text{ or }n>1,\\ 2\text{, if }p=17. \end{array}\right. $$
4.5 Combining all results
From what we have proven so far we get:
If p ≡ 3 mod 4 then
It follows that \(\mathcal {U}_{d_{n}}\in \{4,6\}\) for p≠ 3.
1.
2.
3.
if \(a\in \mathbb {F}_{p}, p\not =3\) then \({\Delta }_{1,d_{n}}(x-\frac {1}{2})=a\) has at most 4 actual solutions and the value 4 is assumed.
If p ≡ 1 mod 4 then
It follows that \(\mathcal {U}_{d_{n}}=2\) if p = 17 and n = 1 and \(\mathcal {U}_{d_{n}}=3\) otherwise. This ends the proof of the uniformity part of theorem 2.1.
1.
2.
3.
if \(a\in \mathbb {F}_{p}\) then \({\Delta }_{1,d_{n}}(x-\frac {1}{2})=a\) has at most 3 actual solutions if either p≠ 17 or n > 1 and the value 3 is assumed in these cases.
4.
if \(a\in \mathbb {F}_{p},p=17\) then \({\Delta }_{1,d_{n}}(x-\frac {1}{2})=a\) has at most 2 actual solutions and the value 2 is assumed.
4.6 Proof of the permutation property for p ≡ 3 mod 4 and Theorem 2.3
By remark 1.2 the mapping \(x^{d_{n}},d_{n}=\frac {p^{n}-1}{2}+p^{\frac {n+1}{2}}+1\) is a permutation iff gcd(dn,pn − 1) = 1, which is what we will show now.
As \(\frac {p^{n}-1}{2}\) is odd also dn odd. Thus any element dividing dn and pn − 1 is odd and therefore divides \(\frac {p^{n}-1}{2}\). Hence it also divides \(d_{n}-\frac {p^{n}-1}{2}=p^{\frac {n+1}{2}}+1\). It follows that
We will show that gcd\(\left (p^{\frac {n+1}{2}}+1,{p^{n}-1}\right )\) equals 2. From this the assertion follows.
$$ \begin{array}{@{}rcl@{}}\gcd(d_{n},p^{n}-1)=\gcd\left( p^{\frac{n+1}{2}}+1,\frac{p^{n}-1}{2}\right)=\frac{\gcd\left( p^{\frac{n+1}{2}}+1,{p^{n}-1}\right)}{2}.\end{array} $$
(24)
Multiplying \(p^{\frac {n+1}{2}}+1\) by \(p^{\frac {n-1}{2}}-1\) and subtracting p(pn − 1) gives − p + 1. Therefore the above gcd divides p − 1. It is
As the gcd divides p − 1 it also divides \((p-1){\sum }_{i=0}^{\frac {n-1}{2}}p^{i}\) and consequently the difference
Thus gcd\((p^{\frac {n+1}{2}}+1,p^{n}-1)=2\) and from the identity given in (24) the permutation property follows.
$$p^{\frac{n+1}{2}}+1=p^{\frac{n+1}{2}}-1+2=(p-1)\sum\limits_{i=0}^{\frac{n-1}{2}}p^{i}+2.$$
$$(p-1)\sum\limits_{i=0}^{\frac{n-1}{2}}p^{i}+2-(p-1)\sum\limits_{i=0}^{\frac{n-1}{2}}p^{i}=2.$$
In the same vein Theorem 2.3 is proved.
This ends the proof of the Theorem 2.1 and Theorem 2.3.
4.7 Proof of Theorem 2.2
4.7.1 Proof of the permutation property
At first we will show that \(x^{d^{\prime }_{n}},\) where
is the inverse of \(x^{d_{n}}\). We will prove the case n ≡ 3 mod 4 by showing that \(d_{n}\cdot d^{\prime }_{n}=1 \bmod 3^{n}-1\). From this the assertion follows for this case. We have
which is even as \(\frac {n-1}{2}\) is odd for n ≡ 3 mod 4. Therefore \(d^{\prime }_{n}\) is odd.
$$d^{\prime}_{n}=\left\lbrace\begin{array}{l}\frac{3^{\frac{n+1}{2}}-1}{2}, n\equiv 1\bmod 4\\ \frac{3^{n}-1}{2}+\frac{3^{\frac{n+1}{2}}-1}{2}, n\equiv 3\bmod 4 \end{array}\right.$$
$$\frac{3^{\frac{n+1}{2}}-1}{2}=\sum\limits_{i=0}^{\frac{n-1}{2}}3^{i},$$
We have
As \(d^{\prime }_{n}\) is odd it is \(x^{\frac {3^{n}-1}{2}d^{\prime }_{n}}=\chi _{n}(x)^{d^{\prime }_{n}}=\chi _{n}(x)\). We get that
The second term of the sum is equal to
We have that \({3^{\frac {n+1}{2}}+1}\) is even and therefore
over \(\mathbb {F}_{n}^{\times }\). Thus (25) simplifies to \(1+\frac {3^{n}-1}{2} \bmod 3^{n}-1\). The addition of both simplifications gives
as requested.
$$\begin{array}{l}d_{n}\cdot d^{\prime}_{n}=\\\left( \frac{3^{n}-1}{2}\right)\left( \frac{3^{n}-1}{2}+\frac{3^{\frac{n+1}{2}}-1}{2}\right)+ \left( 3^{\frac{n+1}{2}}+1\right)\left( \frac{3^{n}-1}{2}+\frac{3^{\frac{n+1}{2}}-1}{2}\right) \bmod 3^{n}-1. \end{array}$$
$$\frac{3^{n}-1}{2}d^{\prime}_{n}=\frac{3^{n}-1}{2}\bmod 3^{n}-1.$$
$$ \begin{array}{@{}rcl@{}}\left( 3^{\frac{n+1}{2}}+1\right)\left( \frac{3^{n}-1}{2}\right)+1+\frac{3^{n}-1}{2}\bmod 3^{n}-1.\end{array} $$
(25)
$$x^{\left( {3^{\frac{n+1}{2}}+1}\right)\left( \frac{3^{n}-1}{2}\right)}=\chi_{n}\left( x\right)^{{3^{\frac{n+1}{2}}+1}}=1=x^{0}$$
$$d_{n}\cdot d^{\prime}_{n}=1+\frac{3^{n}-1}{2}+\frac{3^{n}-1}{2}=1 \bmod 3^{n}-1$$
The case n ≡ 1 mod 4 is proven analogously.
4.7.2 Proof of \(3\leq \mathcal {U}_{d_{n}}\leq 4\)
A direct computation shows that the \(\mathcal {U}_{d_{1}}=3\).
The proof for n > 1 is exactly as in the general case. Therefore we restrict to prove that ϕ2 and ϕ3 never contribute a suitable solution at the same time. Then from what we have proven in Sections 4.3 and 4.4 adapted to p = 3 it follows that \(3\leq \mathcal {U}_{d_{n}}\leq 4\).
In the case p = 3 the zeros of ϕ2 and ϕ3 are the roots
and
From Section 4.3 we get that the two roots of ϕ2(x) yield suitable solutions of fundamental (4) only if χ(−a − 1) = 1 which simplifies to χ(a + 1) = − 1 since χ(− 1) = − 1. Moreover the suitable solutions fulfill the character condition χ(x + 1) = − 1,χ(x − 1) = 1 only if
Therefore ϕ2 contributes two actual solutions only if χn(b − a) = 1. Similarly one shows, that ϕ3 contributes two actual solutions only if χn(a − 1) = 1 and \(\chi _{n}\left (\frac {b-a}{a-1}\right )=-1,\) which leads to χn(b − a) = − 1. We conclude that ϕ2 and ϕ3 never contribute actual solutions at the same time as long as a≠ ± 1. This case is covered by the above direct computation as again we have that \({\Delta }_{d_{n},1}(x-\frac {1}{2})^{-1}(a)\subset \mathbb {F}_{3}\) for \(a\in \mathbb {F}_{3}\). As the mapping has uniformity 3 over \(\mathbb {F}_{3}\) it follows that \(\mathcal {U}_{d_{n}}\in \{3,4\}\). This proves the corollary.
$$ \pm\left( a+1\right)^{\frac{3^{\frac{n+1}{2}}-1}{2}} $$
$$ \pm\left( a-1\right)^{\frac{3^{\frac{n+1}{2}}-1}{2}}. $$
$$ \chi_{n}\left( \left( \pm\left( a+1\right)^{\frac{3^{\frac{n+1}{2}}-1}{2}}+1\right)\cdot\left( \pm\left( a+1\right)^{\frac{3^{\frac{n+1}{2}}-1}{2}}-1\right)\right)= $$
$$ \chi_{n}\left( \frac{b+1}{a+1}-1\right)=\chi_{n}\left( \frac{b-a}{a+1}\right)=-1. $$
A question arising is if we are able to compute the exact uniformity for n > 1. In [8] it was shown that from what we have proven so far we get that \(\mathcal {U}_{d_{n}}=4\) for \(\mathbb {F}_{3^{n}}, n>1\) iff the following character sum is non-zero.
$$ \begin{array}{@{}rcl@{}} \frac{1}{2^{5}}\sum\limits_{\alpha\in\mathbb{F}_{n}}(1+\chi_{n}(\alpha+1))(1+\chi_{n}(\alpha-1))(1-\chi_{n}(\alpha))\cdot\\ \left( 1+\chi_{n}\left( \left( \alpha+\alpha^{3^{\frac{n+1}{2}}}+1\right)^{\frac{3^{\frac{n+1}{2}}-1}{2}}-1\right)\right)\cdot\\ \left( 1-\chi_{n}\left( \left( \alpha+\alpha^{3^{\frac{n+1}{2}}}+1\right)^{\frac{3^{\frac{n+1}{2}}-1}{2}}+1\right)\right) \end{array} $$
(26)
Standard techniques to prove that such a character sum is non-zero make use of the Weil bound (see theorem 3.3). This bound is useless as the degree of the conjugation \(x\mapsto x^{3^{\frac {n+1}{2}}}\) is to high. It is an open problem how to evaluate such kind of character sums. It is conjectured that this sum is non-zero.
5 Further research
In this paper we gave a general family of low uniformity which is bijective for p ≡ 3 mod 4. If p = 3 the family has uniformity of at most 4 and its inverse family has a simple and closed description. To compute the uniformity we made use of the multivariate method and showed that it is a universal tool to do so. The advantage of this approach is that it yields concrete paramterizations for the solutions of \({\Delta }_{d_{n},1}\left (x-\frac {1}{2}\right )=a\). This is particularly useful if one wants to compute the cross-correlation. An example is the proof given in [6] for ternary decimations of Welch and Niho type. Many families of low uniformity can be represented as in this paper by power mappings, where a conjugation of the form \(p^{\frac {n+1}{2}}\) or \(p^{\frac {n}{2}}\) is involved as well as the quadratic character \(\chi _{p^{n}}\). Computing good upper bounds the uniformity by the multivariate method is often an almost routine matter whereas determining the exact uniformity leads to the problem of showing that a character sum as given in (26) is nonzero. Standard techniques to do so make use of the Weil bound. This is very often not applicable for the character sums arising from that kind of power mappings. An approach to show that such kind of character sums are non-zero would be an enormous step forward in the theory of computing the uniformity of power mappings in odd characteristic. Another approach to compute the exact uniformity for the mappings given in theorem 2.2 could be to analyze if the technique to treat the Δ-mapping in the proof given in [6] for the ternary decimations of Welch and Niho type can be adapted. This proof made extensively use of the fact that these decimations yield permutations \(x^{d_{n}}\) with a simple description for the inverse.
For applications in cryptography it is also of interest to analyze if the mappings presented here are strong against linear cryptanalysis and related attacks when employed in a block- or stream cipher. To compute the cross-correlation would be a fruitful next step in this direction.
Acknowledgments
Open Access funding provided by Projekt DEAL.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.