Construction of a cryptographic function based on Bose-type Sidon sets

1.   Introduction

The security of the block cipher in symmetric cryptography, is based, in some cases, on vectorial Boolean functions $\mathbb{F}_2^n\to\mathbb{F}_2^m$ called substitution boxes (S-Box), which satisfy the properties of high nonlinearity and low differential uniformity that make those functions resistant to the linear cryptanalysis and differential cryptanalysis introduced by Mitsuru Matsui in ^[1], and Eli Biham and Adi Shamir in ^[2], respectively. The main ideas in those cryptanalyses are (i) to approximate the vectorial Boolean function by using affine functions, and (ii) to analyze how the differences in the input can affect the resulting difference in the output. Functions with high nonlinearity and low differential uniformity are highly resistant to the two cryptanalysis methods mentioned above. The notion of nonlinearity and differential uniformity can be generalized to algebraic structures other than $\mathbb{F}_2^n$, which allow us to talk about the nonlinearity and differential uniformity of functions between any two finite Abelian groups.

The designing and construction of cryptographic functions resistant to attacks is a complex task, and often based on algebraic methods, random generation, and heuristic designs ^[3,4,5,6]. Each of these methods has advantages and disadvantages over most of the desirable properties of a cryptographic function; for instance, with algebraic constructions, we analyze what properties the functions satisfy, but with heuristic designs, we obtain functions with several properties from their construction ^[7]. However, if we consider an application from $\mathbb{F}_2^n$ to $\mathbb{F}_2^m$, then there are $2^{m2^n}$ functions; that is, there exist many even in a few variables, which implies a hard problem in a computational search. The abundance of vectorial Boolean functions suggests to us that it is usually impossible to solve the problem of the construction of "good" cryptographic functions using only computational searching, and so it is necessary to introduce more effective methods to design new and better vectorial Boolean functions that can be efficiently implemented in electronic devices ^[3].

Functions between two Abelian finite groups $A$ and $B$ with the same cardinality and the smallest possible nonlinearity are called perfect nonlinear (PN) functions. These functions are related to Sidon sets (a subset of an additive group with the property that all sums of two elements in this set are different), since a function is APN if and only if its associated graph is a Sidon set in the product group $A\times B$. This is one of the reasons we focus on an algebraic construction to introduce new cryptographic functions that arise from the construction of a finite Sidon set due to Bose ^[8]. The main contribution of this paper is the construction of a new set of functions with good linear and differential properties based on the construction of Sidon sets. This set of functions is 2-to-1, that is, functions in which each output value has zero or two possible preimages ^[9]. We know that 2-to-1 functions play an important role in cryptography because they can be used to create reversible functions that are not 1-to-1, which can make it harder for attackers to break encryption schemes or find collisions in hash functions ^[10,11]. Moreover, they are often used in the construction of APN functions, bent functions, and binary linear codes ^[12,13,14].

The remainder of this paper is as follows: Section 2 introduces definitions related to differential uniformity and nonlinearity in Abelian groups. Section 3 presents the construction of our function and some of its properties, including differential uniformity and symmetry. We then illustrate its linearity, and list the number of functions that exist for each $n\in\mathbb{N}$ based on our construction. Finally, Section 4 presents some conclusions and future research directions.

2.   Perfect nonlinear functions and nonlinearity

The resistance of functions to cryptanalysis is characterized by two quantities: (ⅰ) nonlinearity, which measures the resistance of a function to linear cryptanalysis, and (ⅱ) differential uniformity, which measures the resistance of a function to differential cryptanalysis. So, we want to construct cryptographic functions with optimal nonlinearity and differential uniformity properties, concepts introduced in this section.

Let $A$ and $B$ denote two non-empty Abelian groups.

Definition 2.1. Let $f:A\to B$ be a function and let $a\in A$. The derivative of $f$ in $a$ is the function

A differential of $f$ with input difference $a$ and output difference $b$ is given by

The number of solutions to (2.1) is denoted by $\delta(a, b)$, that is

Now, if $\Delta_f$ denotes the positive integer

then $f$ is said to be differentially $\Delta_f-$uniform. Note that $\Delta_f\geq|A|/|B|$. In particular, if $\Delta_f = |A|/|B|$, then $f$ is called a perfect nonlinear (PN) function ^[15]. Note also that if $|A| = |B|$, then $\Delta_f = 1$, which implies that (2.1) has one solution. We know that PN functions do not exist in fields of characteristic 2, since if $x$ satisfies $f(x+a)-f(x) = b$, then so does $x+a$. This is the reason for introducing the following definition:

Definition 2.2. A function $f$ is an almost perfect nonlinear (APN) function if $\Delta_f = 2|A|/|B|$.

In particular, note that if $|A| = |B|$, then $\Delta_f = 2$, that is, (2.1) has at most two solutions ^[15].

If we consider a Boolean function $f:\mathbb{F}_2^n\to\mathbb{F}_2$ of $n$ variables, then the nonlinearity $\mathcal{NL}(f)$ of $f$ is the minimum Hamming Distance* between $f$ and all affine functions $\varphi_a(x) = a\cdot x+c$, with $a\in\mathbb{F}_2^n$ and $c\in\mathbb {F}_2$. That is

*The Hamming Distance between $f$ and $g$ is $d(f, g) = |\{x\in\mathbb{F}_2^n; \ f(x)\neq g(x)\}|$.

However, an equivalent concept to nonlinearity that uses a special case of the discrete Fourier transform called the Walsh transform (or Walsh–Hadamard transform) is a useful tool when we want to study the nonlinearity of a function.

Now, consider $A = \mathbb{Z}_q$ and $B = \mathbb{Z}_r$ for the $q$ and $r$ integers. Let $\omega_q\in\mathbb{C}$ and $\omega_r\in\mathbb{C}$ denote the $q-$th and $r-$th roots of unity in $\mathbb{C}$. The expression $x\mapsto \omega_q^{ax}$ defines a character in $\mathbb{Z}_q$ for all $a\in\mathbb{Z}_q$. Similarly, the set of characters in $\mathbb{Z}_r$ for all $b\in\mathbb{Z}_r$ is defined by $y\mapsto \omega_r^{by}$ ^[15].

Definition 2.3. The Walsh–Hadamard transform of $f:\mathbb{Z}_q\to \mathbb{Z}_r$ at $a\in \mathbb{Z}_q$ and $b\in \mathbb{Z}_r$ is defined as

where $\overline{\omega}_q$ is the complex conjugate of $\omega_q$.

For the different possible parameter values $(a, b)$, this formula compares every constant multiple of $f$ against every linear function $ax$; the greatest value is indicative of the closeness of $f$ to such a linear function, so the Walsh–Hadamard transform helps us measure the nonlinearity of a function $f$ according to the following definition:

Definition 2.4. The linearity of a function $f:\mathbb{Z}_q\to \mathbb{Z}_r$ is defined by

From ^[16], we know that if $f:\mathbb{Z}_q\to \mathbb{Z}_r$, then $\sqrt{q}\leq\mathcal{L}(f)\leq q$. Functions that reach the lower bound have optimal linearity and are called bent functions.

Definition 2.5. Let $f:\mathbb{Z}_q\to \mathbb{Z}_r$. We define the nonlinearity of $f$ by

Note that nonlinearity actually measures the distance between $f$ and all linear affine functions. Furthermore, also that $\mathcal{N}\mathcal{L}(f) = 0$ if and only if $f$ is an affine linear function. It is clear that a bijection and its inverse have the same nonlinearity ^[16].

Finally, from ^[17], we know that a function $f:\mathbb{F}_2^n\to\mathbb{F}_2^m$, with $n\geq2m$ and $n$ even, is perfect nonlinear if and only if it is bent.

3.   The construction

In this section, we present the construction of our function, which is based on the construction of Sidon sets due to Bose ^[8].

Let $G$ denote an additive group. A set $A\subseteq G$ is a Sidon set in $G$ if, for all $a, b, c, d\in A$, we have

That is, $A$ is a Sidon set if all the sums of two elements of $A$ are different. Since $a+b = c+d$ if and only if $a-c = d-b$, Sidon sets can also be defined as those with the property that all nonzero differences of pairs of elements are distinct. In particular, the construction of Sidon sets due to Bose is as follows ^[8].

Theorem 3.1. Let $q = p^n$ with $p$ a prime number and $n\in\mathbb{N}$. Let $(\mathbb{F}_q, +, \cdot)$ be the finite field with $q$ elements, and $\mathbb{F}_{q^2}$ be an algebraic extension of degree two over $\mathbb{F}_q$. If $\theta$ is a primitive element of $\mathbb{F}_{q^2}$, then

is a Sidon set in $\mathbb{Z}_{q^2-1}$ with $q$ elements.

From ^[18], we know that the set $\theta+\mathbb{F}_q$ is a Sidon set with $q$ elements in the multiplicative group $\mathbb{F}_{q^2}^*$. Furthermore, we know that isomorphisms preserve the Sidon property, so using the discrete logarithm in base $\theta$, we verify that set the $\mathcal{B}_q(\theta)$ is a Sidon set with $q$ elements in the group $\mathbb{Z}_{q^2-1}$, which illustrates a proof of Theorem 3.1.

Example 3.1. Let $q = 2^4$. If we take the primitive element $\theta$ over $\mathbb{F}_{2}$ such that $\theta^8+\theta^4+\theta^3+\theta^2+1 = 0$, then we can construct the Sidon set in $\mathbb{Z}_{255}$ given by

According to the work in ^[18], we know that $\mathcal{B}_q(\theta)$ satisfies the following properties, where $[1, q]$ denotes the set of integers $\{1, \dots, q\}$.

Proposition 3.1. If $\mathcal{B}_q(\theta)$ is the set in (3.1), then

B1) If $b\in \mathcal{B}_q(\theta)$, then $b\not\equiv0\mathrm{\, mod}\, {(q+1)}$.

B2) If $a, b\in \mathcal{B}_q(\theta)$ and $a\neq b$, then $a\not\equiv b\mathrm{\, mod}\, {(q+1)}$.

B3) $\mathcal{B}_q(\theta)\mathrm{\, mod}\, {(q+1)}: = \{a\mathrm{\, mod}\, {(q+1)}:a\in \mathcal{B}_q(\theta)\} = [1, q]$.

Proof. We verify property B2) by contradiction. Suppose $a\equiv b\mathrm{\, mod}\, {(q+1)}$, that is, there exists $n\in\mathbb{Z}$ such that $a-b = n(q+1)$. Note that $\theta^{q+1}$ generates $\mathbb{F}_q^*$, so $\theta^{a-b} = \theta^{n(q+1)}\in\mathbb{F}_q^*$. Now, let $a, b\in \mathcal{B}_q(\theta)$, there exist $k_1, k_2\in\mathbb{F}_q$ with $k_1\neq k_2$, such that $a = \log_{\theta}(\theta+k_1)$ and $b = \log_{\theta}(\theta+k_2)$, implying that $\theta^a = \theta+k_1$ and $\theta^b = \theta+k_2$. Thus, $\theta^{a-b} = (\theta+k_1)/(\theta+k_2)$. Since $\theta^{a-b}\in\mathbb{F}_q^*$, there exists $c\in\mathbb{F}_q^*$ such that $(\theta+k_1)/(\theta+k_2) = c$. So, $(1-c)\theta = ck_2-k_1$. Because $c\neq1$, then $\theta = (ck_2-k_1)(1-c)^{-1}\in\mathbb{F}_q^*$, which is a contradiction. □

Proposition 3.1 means that for each $x\in[1, q]$, we can find a unique $b\in \mathcal{B}_q(\theta)$ such that $b\mathrm{\, mod}\, {(q+\; 1)} = x$, i.e., there exists a bijective relationship between the sets $[1, q]$ and $\mathcal{B}_q(\theta)\mathrm{\, mod}\, {(q+1)}$.

The authors in ^[19,20] describe the following relationship between Sidon sets and APN functions: A function $F:\mathbb{F}_2^n\to\mathbb{F}_2^n$ is APN if and only if the set $\mathcal{G}_F = \{(x, F(x)): x\in\mathbb{F}_2^n\}$ is a Sidon set in the group $(\mathbb{F}_2^n\times\mathbb{F}_2^n, +)$. It is common to refer to $\mathcal{G}_F$ as the graph of $F$. This relationship gives us an idea of how to construct cryptographic functions from known constructions of Sidon sets on finite Abelian groups, that is, we take Sidon sets in one dimension and try to put them in two dimensions via some transformation that preserves the Sidon property; in particular, we use the isomorphism guaranteed by the Chinese remainder theorem to put the set $\mathcal{B}_q(\theta)$ in two dimensions.

Note that if $q = 2^n$, then we have that gcd$(q+1, q-1) = 1$, and so by the Chinese remainder theorem, we have that $\mathbb{Z}_{q^2-1}$ is isomorphic to $\mathbb{Z }_{q+1}\times\mathbb{Z}_{q-1}$. So if $\mathcal{B}_q(\theta)$ is a Sidon set given by (3.1), then each element $b\in\mathcal{B}_q(\theta)$ can be represented as an ordered pair in $\mathbb{Z}_{q+1}\times\mathbb{Z}_{ q-1}$ as follows:

According to Proposition 3.1, B3), note that if we run $b$ in $\mathcal{B}_q(\theta)$, then the set of first coordinates of pair (3.2) coincides with the set $[1, q]$; it allows us to define a set of functions with a common domain $[1, q]$, which, when endowed with the sum modulo $q$, can be identified with $\mathbb{Z}_q$, that is $([1, q], +_{\mathrm{\, mod}\, {q}})\equiv\mathbb{Z}_q$. The co-domain of this set of functions is obtained by reducing the set $\mathcal{B}_q(\theta)$ modulo $q-1$, as indicated by the second coordinate of the pair (3.2). This set of functions is our main contribution to this work, and they have, in particular, properties of symmetry, good differential uniformity, and good nonlinearity. Moreover, since Proposition 3.1 is valid for all $q$, we observe that if $q = p^n$ with $p > 2$, then the construction of these functions is still valid and their properties are preserved, except for good nonlinearity.

Definition 3.1. Let $\mathcal{B}_q(\theta)$ be a Sidon set defined by (3.1). Identify the set $[1, q]$ with the group $\mathbb{Z}_q$ and consider $\mathcal{B}_q(\theta)\mathrm{\, mod}\, {(q-1)}\subseteq\mathbb{Z}_{q-1}$. Define the function $f_q:\mathbb{Z}_q\to\mathbb{Z}_{q-1}$ as

for $b\in \mathcal{B}_q(\theta)$ such that $b\mathrm{\, mod}\, {(q+1)} = x$.

We denote the range of $f_q$ as the sequence $R(f_q) = [f_q(x)]$. The function $f_q$ can be constructed based on the following procedure, where step 2 is valid because of Proposition 3.1, B2).

Step 1. Take $x\in\mathbb{Z}_{q}$.

Step 2. Find the unique $b\in \mathcal{B}_q(\theta)$ such that $b\equiv x\mathrm{\, mod}\, {(q+1)}$.

Step 3. Take $f_q(x) = b\mathrm{\, mod}\, {(q-1)}$.

Note that $b$ depends on $x$, so we can denote $b$ as $b_x$. In this way, the diagram in Figure 1 illustrates the procedure described above.

Example 3.2. Let

be the Sidon set in Example 3.1. We construct the function $f_{16}:\mathbb{Z}_{16}\to\mathbb{Z}_{15}$ as follows:

● If $x = 1$, then $b = 1\in \mathcal{B}_{2^4}(\theta)$ satisfies $1\mathrm{\, mod}\, {17} = 1$, which implies that $f_{16}(1) = 1\mathrm{\, mod}\, {15} = 1$.

● If $x = 2$, then $b = 223\in \mathcal{B}_{2^4}(\theta)$ is the unique element that satisfies $223\mathrm{\, mod}\, {17} = 2$, which implies that $f_{16}(2) = 223\mathrm{\, mod}\, {15} = 13$.

● If $x = 3$, then $b = 3\in \mathcal{B}_{2^4}(\theta)$ satisfies $3\mathrm{\, mod}\, {17} = 3$, and so $f_{16}(3) = 3\mathrm{\, mod}\, {15} = 3$.

● If $x = 4$, then $b = 157\in \mathcal{B}_{2^4}(\theta)$ is the unique element that satisfies $157\mathrm{\, mod}\, {17} = 4$, which implies that $f_{16}(4) = 157\mathrm{\, mod}\, {15} = 7$.

● We repeat the above procedure for the other elements of $\mathbb{Z}_{16}$.

Figure 2 illustrates the function $f_{16}:\mathbb{Z}_{16}\to\mathbb{Z}_{15}$ with a range given by

Note that we take $0: = 16$ in $\mathbb{Z}_{16}$, so Figure 2 shows a clear symmetry in the range of the function $f_{16}$. In general, we have the following result:

Theorem 3.2. If $f_q:\mathbb{Z}_q\rightarrow \mathbb{Z}_{q-1}$ is the function defined in (3.3), then for all $x\in\mathbb{Z}_q$ we have

i) $f_q(x) = f_q(q+1-x)$.

ii) $f_q((q+1)/2+x) = f_q((q+1)/2-x)$ for $p > 2$ (i.e., $f_q$ is symmetric with respect to $x = (q+1)/2$).

Proof. ⅰ) Let $x, q+1-x\in[1, q]$. Assume that

with $b_1, b_2\in \mathcal{B}_q(\theta)$. According to the definition of $f_q$, we know that

Consider the following two cases:

Case 1. If $b_1 = b_2$, then $q+1-x\equiv x\mathrm{\, mod}\, {(q+1)}$. Since $1\leq x, q+1-x\leq q < q+1$ we have that $q+1-x = x$, or $x = (q+1)/2$ (only for $q$ odd), which implies $f_q(x) = f_q(q+1-x)$, that is, $r = s$.

Case 2. If $b_1\neq b_2$, then there are $k_1, k_2\in\mathbb{F}_q$ with $k_1\neq k_2$ such that

that is

Let $\gamma: = \theta^{b_1-b_2} = \frac{\theta+k_1}{\theta+k_2}$. Note that $\gamma\neq1$, since otherwise $k_1 = k_2$. Moreover, $\gamma\notin\mathbb{F}_q^*$ because $\theta$ is a primitive element over $\mathbb{F}_q$ of degree two, so $\gamma\in\mathbb{F}_{q^2}^*\setminus\mathbb{F}_q^*$. Because $\mathbb{F}_q^*$ and $\langle \theta^{q-1}\rangle$ (the group generated by $\theta^{q-1}$) are two subgroups of $\mathbb{F}_{q^2}^*$ that only intersect at $1$ if $q$ is even or $\pm1$ if $q$ is odd, and because $\gamma\notin\mathbb{F}_q^*$, we have that $\gamma\in\langle \theta^{q-1}\rangle$. Therefore, there exists $t\in\mathbb{Z}$ such that $\gamma = \theta^{t(q-1)}$, from which $\theta^{b_1-b_2} = \theta^{t(q-1)}$. Since $b_1-b_2\equiv r-s\mathrm{\, mod}\, {(q-1)}$, then $b_1-b_2 = n(q-1)+(r-s)$ for some $n\in\mathbb{Z}$, implying that

from which $n(q-1)+(r-s)\equiv t(q-1)\mathrm{\, mod}\, {(q^2-1)}$, that is, $(r-s)\equiv 0\mathrm{\, mod}\, {(q-1)}.$ Because $0\leq r, s < q-1$ we have that $r = s$.

ⅱ) Is similar to the proof of ⅰ). □

Now, we know in $\mathbb{Z}_q$ that $-x = q-x$, so in $\mathbb{Z}_{q+1}$ and for $b_1, b_2\in \mathcal{B}_q(\theta)$, we have

in $\mathbb{Z}_{q+1}$. That is, $b_1+b_2\equiv0\mathrm{\, mod}\, {(q+1)}$ and $b_1-b_2\equiv0\mathrm{\, mod}\, {(q-1)}$. The following corollary formalizes this property, in which the system of congruences is a particular case of the multivariable Chinese Remainder theorem.

Corollary 3.1. For a given $x\in \mathcal{B}_q(\theta)$, there exist a $y\in \mathcal{B}_q(\theta)$ not necessarily different from $x$ such that

Example 3.3. Let

be the Sidon set in Example 3.1. Table 1 illustrates Corollary 3.1.

Note that Theorem 3.2 establishes that $f_q(x)$ is symmetric and consequently a 2-to-1 function according to the next definition ^[9].

Definition 3.2. Let $A$ and $B$ be two finite sets, and let $f$ be a mapping from $A$ to $B$. Function $f$ is called a $2$-to-$1$ mapping if one of the following two cases holds:

i) $|A|$ is even, and for any $b\in B$, it has either $2$ or $0$ preimages of $f$.

ii) $|A|$ is odd, and for all but one $b\in B$, it has either $2$ or $0$ preimages of $f$, and the exception element has exactly one preimage.

From Theorem 3.2, ⅰ), note that the conditions of Definition 3.2 are satisfied, and from Theorem 3.2, ⅱ), the exception element is $2^{-1}\mathrm{\, mod}\, {q} = \frac{q+1}{2}$. It implies the next corollary.

Corollary 3.2. For all prime numbers $p$ and all $n\in\mathbb{N}$, the function $f_{q}$ is 2-to-1.

One important property in cryptographic applications is low differentiability, since functions with low differential uniformity are resistant to differential attacks ^[2]. Fortunately, the function $f_q$ has this property, as we demonstrate in the following theorem.

Theorem 3.3. For all prime numbers $p$ and all $n\in\mathbb{N}$, the function $f_q$ is differentially 2-uniform.

Proof. Let $a\in\mathbb{Z}_q\setminus{\{0\}}$ and $b\in\mathbb{Z}_{q-1}$. Consider the equation

From the definition of $f_q$ we know that there exist $b_1, b_2\in \mathcal{B}_q(\theta)$ such that

which implies that $b_1+b_2\equiv2x+a\mathrm{\, mod}\, {(q+1)}$, and so there exists $m\in\mathbb{N}$ such that

Note also from the definition of $f_q$ that

so (3.4) is equivalent to $b_1-b_2\equiv b\mathrm{\, mod}\, {(q-1)}$, that is, there exists $n\in\mathbb{N}$ such that

and thus, from (3.5) and (3.6), we have

That is

So far, we have proved that (3.4) is equivalent to (3.7). Next, to show that (3.4) has at most 2 solutions, we consider the following cases for $q$:

1) If $q = 2^n$, then gcd$(2, q-1) = 1$, and so (3.7) has one solution.

2) If $q = p^n$ and $p\neq2$, then gcd$(2, q-1) = 2$, but note that $2|(-2m+2b_2+b-a)$ if and only if $2|(b-a)$. So it is sufficient to find $b\in\mathbb{Z}_{q-1}$ and $a\in\mathbb{Z}_q\setminus{\{0\}}$ such that $b-a$ is an even number to guarantee that (3.7) has exactly two solutions.

□

3.1.   Enumeration of the functions $f_q$

Note that the function $f_q$ depends on the Sidon set $\mathcal{B}_q(\theta)$ given in (3.1); thus, if we want to count the functions $f_q$ we must first count the sets $\mathcal{B}_q(\theta)$. Note also that for a fixed $q = p^n$, the construction of the Sidon set $\mathcal{B}_q(\theta)$ depends on a primitive element $\theta\in\mathbb{F}_{q^2}^*$, so we can wonder about the behavior of these sets when we vary the primitive element within the field. We have the following:

Theorem 3.4. If $\alpha$ and $\theta$ are conjugates, then $\mathcal{B}_q(\theta) = \mathcal{B}_q(\alpha)$.

Proof. If $\alpha$ and $\theta$ are conjugates, then $\alpha = \theta^{p^i}$ for some $i\in\{1, \dots, 2n-1\}$. Let $\log_{\alpha}(\alpha+a)\in \mathcal{B}_q(\alpha)$. Since $\alpha^{q+1}$ generates $\mathbb{F}_{p^n}^*$ there exists $m\in\mathbb{Z}$ such that $a = \alpha^{m(q+1)} = \theta^{m(q+1)p^i}$, thus

Note that $\theta^{q+1}$ also generates $\mathbb{F}_{p^n}^*$, so $b: = \theta^{m(q+1)}\in\mathbb{F}_{p^n}^*$. If we apply the base interchange formula on the right side of (3.8), then

Therefore, $\log_{\alpha}(\alpha+a)\in \mathcal{B}_q(\theta)$, which implies that $\mathcal{B}_q(\alpha)\subseteq \mathcal{B}_q(\theta)$. Now, because $| \mathcal{B}_q(\alpha)| = | \mathcal{B}_q(\theta)|$, we have that $\mathcal{B}_q(\alpha) = \mathcal{B}_q(\theta)$. □

Computational calculations indicate that the reciprocal of Theorem 3.4 is valid, but its proof is strongly related to the theory of multipliers on relative difference sets, of which we do not know the solution. So we conjecture the following:

Conjecture 3.1. If $\mathcal{B}_q(\theta) = \mathcal{B}_q(\alpha)$, then $\alpha$ and $\theta$ are conjugates.

Theorem 3.4 helps us to establish an upper bound for the number of different Bose-type Sidon sets that exist for each $p\geq2$ and $n\geq1$, and since the construction of our set of functions depends on these sets, it will also help us to establish an upper bound for the number of different functions $f_q$ that exist.

Theorem 3.5. Let $q = p^n$. For each $p\geq2$ and each $n\in\mathbb{N}$, there exist at most $\varphi(q^2-1)/2n$ different Sidon sets $\mathcal{B}_q(\theta)$.

Proof. Note that, if $\theta$ is a primitive element of $\mathbb{F}_{q^2}$ over $\mathbb{F}_p$, then its $2n$ conjugates $\theta, \theta^p, \dots, \theta^{p^{2n-1}}$ are also primitives, so from Theorem 3.4, it generates the same Sidon set $\mathcal{B}_q(\theta)$. Furthermore, because there are $\varphi(q^2-1)$ primitive elements in $\mathbb{F}_{q^2}$ ($\varphi$ is Euler's phi function), we have that actually there exist $\varphi(q^2-\; 1)/2n$ different primitive elements that are not conjugated to each other, thus these primitive elements generate at most $\varphi(q^2-\; 1)/2n$ different Sidon sets $\mathcal{B}_q(\theta)$. □

Note that if Conjecture 3.1 is true, then we obtain the equality in Theorem 3.5 since the $\varphi(q^2-\; 1)/2n$ different primitive elements not conjugate with each other would generate exactly $\varphi(q^2-1)/2n$ sets $\mathcal{B}_q(\theta)$.

Lemma 3.1. Let $p > 2$ and $\theta$ be a primitive element of $\mathbb{F}_{p^2}$. If $c = \frac{p^2-1}{2}+p$, then $\theta^c = \theta+b$ for some $b\in\mathbb{F}_p\setminus{\{0\}}$.

Proof. Note that gcd$(c, p^2-1) = 1$, so $\theta^c$ is another primitive element of $\mathbb{F}_{p^2}$, implying that $\theta^c = a\theta+b$ for some $a, b\in\mathbb{F}_p\setminus{\{0\}}$. Note also that $\theta^c = -\theta^p$, from which $\theta^p = -a\theta-b$, and so $\theta^p+\theta = (1-a)\theta-b$. Because $\theta^p+\theta\in\mathbb{F}_p$, we have $a = 1$. □

Theorem 3.6. Let $p > 2$ and $t\leq\varphi(p^2-1)/2$. Let $\mathcal{A} = \{\mathcal{B}_p(\theta_i): i = 1, \dots, t\}$ be the collection of the $t$ different Bose-type Sidon sets. For each $\mathcal{B}_p(\theta_i)\in\mathcal{A}$ there exist $\mathcal{B}_p(\theta_j)\in\mathcal{A}$, with $i\neq j$ such that

Proof. Let $\theta^i$ be a primitive element such that $\mathcal{B}_p(\theta^i)\in\mathcal{A}$ and $c = \frac{p^2-1}{2}+p$. Take $j = ic$ and note that $\mathcal{B}_p(\theta^j)\in\mathcal{A}$ because $\theta^j$ is also a primitive element; moreover, $\mathcal{B}_p(\theta^j)\neq\mathcal{B}_p(\theta^i)$ since otherwise $\theta^j$ and $\theta^i$ would be conjugates, which is not possible. Now, from Lemma 1, we have that

for some $b\in\mathbb{F}_p\setminus{\{0\}}$. Now, if $\log_{\theta^j}(\theta^j+k_0)\in\mathcal{B}_p(\theta^j)$ for some $k_0\in\mathbb{F}_p$, then from (3.9) we have that

for $k_1\in\mathbb{F}_p$. If we apply the base interchange formula, then

so

that is

This implies that $c\mathcal{B}_p(\theta^j)\subseteq \mathcal{B}_p(\theta^i)$, and because $|c\mathcal{B}_p(\theta^j)| = |\mathcal{B}_p(\theta^i)|$, we have proof that $c\mathcal{B}_p(\theta^j) = \; \mathcal{B}_p(\theta^i)$, and so $\mathcal{B}_p(\theta^j)\mathrm{\, mod}\, {(p-1)} = \mathcal{B}_p(\theta^i)\mathrm{\, mod}\, {(p-1)}$. □

Note again that if Conjecture 3.1 is true, then we could guarantee uniqueness in the set $\mathcal{B}_p(\theta^j)\in\mathcal{A}$. The objective of this section was to count the functions $f_q$, so, in the following theorem, we establish an upper bound for the number of functions for $q = 2^n$ and $q = p$.

Theorem 3.7. Let $q = p^n$ with $n\in\mathbb{N}$. For $p = 2$, there exist at most $\varphi(q^2-1)/2n$ different functions $f_q$, and for $p > 2$ and $n = 1$, there exist at most $\varphi(p^2-1)/4$ different functions $f_p$.

Proof. If $p = 2$, then by the Chinese remainder theorem we have that $\mathbb{Z}_{q^2-1}$ is isomorphic to $\mathbb{Z }_{q+1}\times\mathbb{Z}_{q-1}$ (denoted by $\mathbb{Z}_{q^2-1}\equiv\mathbb{Z }_{q+1}\times\mathbb{Z}_{q-1}$), and because Sidon's property is preserved under isomorphism ^[18], from (3.2) we have that

and the result follows from Theorem 3.5.

Now, if $p > 2$ and $n = 1$, then we simply put the set $\mathcal{B}_p(\theta)$ in the group $\mathbb{Z}_{p+1}\times\mathbb{Z}_{p-1}$ as

and the result follows from Theorem 3.5 and Theorem 3.6. □

Example 3.4. Note that if $q = 2^n$, then gdc$(q-1, q+1) = 1$, and $\varphi(q^2-1)/2n = \varphi(q-1)\varphi(q+1)/2n$, which facilitates the counting of the functions $f_q$. For instance, for $q = 2^4$, there exists $\varphi(15)\varphi(17)/8 = 16$ different functions given by

From [21, Chapter 18], we know that $\limsup\varphi(n)/n = 1$, which means that the order of $\varphi(n)$ is nearly $n$, that is,

So for $p = 2$ and $n$ sufficiently large, we conclude that there exist approximately $2^{2n}/2n$ functions $f_q$. Moreover, from [21, Theorem 328], we know that the function $\varphi(n)$ satisfies

where $\gamma$ is the Euler–Mascheroni constant. So for $q = 2^n$, (3.10) implies that $\varphi(q^2-1)/2n$ is bounded below by

this expression is equivalent to

with $\varepsilon_n\rightarrow0$ when $n\rightarrow \infty$. Hence, for $q = 2^n$, we have that the number of functions $f_q$ is at least

if $n$ is large enough. For $p > 2$ and $n = 1$, similar formulas can be derived.

3.2.   Simulation results

This section illustrates the linearity of $f_q$. We know for $\alpha\neq0$ that $|\hat{f}_q(q-\alpha, (q-1)-\beta)| = |\hat{f}_q(\alpha, \beta)|,$ which, together with Theorem 3.2, reduces by a factor of approximately 4 the number of points required to calculate the linearity of $f_q$. With this fact and the fast Fourier transform, we illustrate in Figures 3 and 4 the linearity of $f_q$ for $q = p$ with $2 < p < 20000$ and $q = 2^n$ with $2\leq n\leq16$. Figure 3b illustrates that the approximation of linearity has a slope of around $0.64$, which leads us to conjecture that the linearity of $f_p$ is bounded below by an affine function that depends on $p$; unfortunately, this implies that $\mathcal{L}(f_{p})$ would be asymptotically closer to the upper bound, that is, $f_p$ is closer to being a linear function.

But when $q = 2^n$, our simulations show a more interesting behavior. For example, for values of $n\in\{4, 5, 6, 7, 8\}$, important in cryptographic applications, the linearity of $f_{2^n}$ is closer to the lower bound, as shown in Figure 4a and Table 2, implying that $f_{2^n}$ has high nonlinearity. Figure 4b illustrates, by means of an exponential regression with a coefficient of determination of $r^2 = 0.998$, that for values of $n$ greater than $16$, the behavior of the linearity of $f_{2^n}$ tends to remain.

Now, when we compare the cases $q = 2^n$ and $q = p$ with $p > 2$, we suspect that the loss of linearity for the second case is due to the fact that there is no an isomorphism between $\mathbb{Z}_{p^2-1}$ and $\mathbb{Z }_{p+1}\times\mathbb{Z}_{p-1}$. Furthermore, note that this behavior still remains when $q = p^n$ with $p > 2$ and $n > 1$.

4.   Conclusions

Our contribution in this work is the construction of a new set of functions that are 2-to-1 functions and differentially 2-uniform, which, for the case $q = 2^n$, present an asymptotic behavior close to the trivial lower bound for its linearity, that is, the asymptotic nonlinearity of function $f_q$ is high. The number of functions that exist for each $n$, with $p = 2$, is of the order $2^{2n}/2n$, and for $n = 1$ and $p > 2$, it is of the order $p^2/4$, so this set of functions grows rapidly as $n$ and $p$ increase, respectively.

Due to the particular way in which we define our function $f_q$, we cannot establish nontrivial bounds for its linearity, so this problem remains open. For instance, through linear and exponential regression, respectively, we conjecture that, i) for $q = p$, there exist two constants $0.5 < \alpha < 1$ and $0 < \beta < 0.5$ such that $\mathcal{L}(f_p)\geq\alpha p+\beta$, and ii) for $q = 2^n$, there exist two constants $\gamma > 1$ and $0 < \mu < 1$ such that $\mathcal{L}(f_{2^n})\leq\gamma e^{\mu n}$. Moreover, note that in this work we emphasize the study of two cases; first, when $q = 2^n$ due to the isomorphism between $\mathbb{Z}_{q^2-1}$ and $\mathbb{Z }_{q+1}\times\mathbb{Z}_{q-1}$, and second, when $q = p$; but the case $q = p^n$ with $p > 2$ and $n > 1$ was not studied in detail, so it remains open to study what other properties the function $f_{p^n}$ satisfies for this case. For instance, we conjecture from Theorem 3.7 that the number of functions $f_q$ that exist for $q = p^n$ with $p > 2$ and $n > 1$ is equal to $\varphi(q^2-1)/4n$, but for proof of this, it is necessary to generalize Lemma 1 and Theorem 3.6 for that case.

Some ciphers, such as SAFER ^[22], use non-binary transformations with "high nonlinearity" and optimal differential uniformity, known in the literature as exponential Welch Costas (EWC) and logarithmic Welch Costas (LWC) functions ^[16,23,24]. Given that for the case $q = 2^n$, the characteristics of our function are similar to those of these functions, we raised concern about the possibility of using our function in a cipher like SAFER.

Author contributions

Julian Osorio: Writing – original draft, Writing – review & editing, Conceptualization, Formal analysis, Investigation; Carlos Trujillo: Conceptualization, Formal analysis, Investigation; Diego Ruiz: Writing – original draft, Writing – review & editing, Conceptualization, Formal analysis, Investigation. All authors have read and approved the final version of the manuscript for publication.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

Authors would like to thank the Universidad del Cauca for funding this paper, and the reviewers for the important feedback, which helped us to improve the quality of this paper. The first author would like to thank MINCIENCIAS (Colombia) for supporting his doctoral studies through "Convocatoria del fondo de ciencia, tecnología e innovación del sistema general de regalías para conformación de una lista de proyectos elegibles para ser viabilizados, priorizados y aprobados por el OCAD en el marco del programa de becas de excelencia doctoral del bicentenario (No. BB 2019 01)."

Conflict of interest

The authors declare no conflict of interest in this paper.