1 Introduction
1.1 Background
In symmetric key cryptography, Substitution boxes (Sboxes) are basic components to perform substitutions. Being the only source of nonlinearity in many wellknown block ciphers such as IDEA, AES and DES [18], they play a central role in obscuring the relationship between the key and ciphertext, the perplexity property depicted by Shannon [32]. The security of such ciphers depends crucially on the quality of the Sboxes used. It is thus important to find new designs of Sboxes with good cryptographic properties with respect to various attacks [3, 19, 26, 39].
Mathematically, Sboxes are vectorial (multioutput) Boolean functions, that is, functions where and are and
dimensional vector spaces over the binary field
respectively.Differential attack, proposed by Biham and Shamir [3], is one of the most fundamental cryptanalytic tools to assess the security of block ciphers. For an bit Sbox , the properties for differential propagations of are captured in the DDT (Difference Distribution Table) of which are given by
The differential uniformity of is defined as
Differential uniformity is an important concept in cryptography as it quantifies the degree of security of the cipher with respect to differential attack if is used as an Sbox in the cipher. In particular, if , then is called an almost perfect nonlinear (APN) function, which offers maximal resistance to differential attacks.
Boomerang attack is an important cryptanalysis technique introduced by Wagner [39] in 1999 against block ciphers involving Sboxes. It can be considered as an extension of the classical differential attack [3]. In a boomerang attack, the target cipher is regarded as a composition of two subciphers, and two differentials are combined and analyzed for the upper and the lower parts of the cipher. The reader is referred to [1, 2, 4, 5, 11, 15, 16, 33] for more details.
At Eurocrypt 2018, Cid, Huang, Peyrin, Sasaki and Song [10]
introduced a new tool called Boomerang Connectivity Table (BCT) to measure the resistance of a block cipher against the boomerang attack. The BCT can be used to more accurately evaluate the probability of generating a right quartet in boomerangstyle attacks, and it provides more useful information when compared with the DDT
[10]. Let be a permutation. The entries of the BCT of are given bywhere denotes the compositional inverse of . The boomerang uniformity of , introduced by Boura and Canteaut in [6], is defined as
The function is called a uniform BCT function.
Roughly speaking, Sboxes with smaller value provide stronger security against boomerangstyle attacks. It was known in [10] that , and if , then , hence APN permutations offer maximal resistance to both differential and boomerang attacks. However, given the difficulty of finding APN permutations in even dimension (This is the Big APN Problem [9]), in even dimension which is the most interesting for real applications, we are contented with the next best, that is, permutations with .
Compared with an abundance of differentially uniform permutations in the literature (see [7, 8, 13, 14, 28] for primary constructions and [29, 31, 34, 35] and the references therein for constructions via the inverse function), it seems much harder to find permutations with uniform BCT in even dimension. Currently only six families of such permutations have been discovered (see [6, 20, 21, 23, 27, 36] for details).
In particular, in [36] the authors studied a class of quadrinomial permutations of the form
where is an odd power of , and derived general conditions on the coefficients ’s under which is a permutation and , and very recently, in [21] and independently in [23] the authors considered the generalized butterfly structure (see [12, 24, 30]) and showed that the closed butterfly yields permutations with uniform BCT under suitable conditions. It was pointed out in [21, 23] that the closed butterfly can be equivalently expressed as the univariate form
(1.1) 
for some special .
The objective of this paper is to study quadrinomials of the form (1.1) for much more general coefficients ’s and investigate conditions under which they become permutations with uniform BCT.
1.2 Statement of the main result
Throughout this paper, let and be both odd integers such that . Let . For any , denote . For any , we consider a general quadrinomial of the form
(1.2) 
Denote
and define
(1.3) 
The set can be partitioned as , where
(1.4) 
Our main result is stated as follows.
Theorem 1.
Remark 1.
In the setting of Therorem 1, if is even, is odd, and is still of the form (1.2), then letting , we can obtain
where
Noting that is odd and , denoting and appealing to Theorem 1, we can still obtain similar conditions to 1)3) under which we can conclude that is a permutation; and . For the sake of simplicity, we omit the details.
Remark 2.
Similar to [37], by using affine equivalence, the coefficients ’s of the quadrinomial in (1.2) may be simplified: if , we may assume that ; by considering for some , we may assume that . Actually when , and , the function was originally studied in [36, 37, 38]. In fact in this case 1) coinsides with the main result of [37] and 2) coinsides with the main result of [36]. On the other hand, using the special parametrization appearing in the papers, one can easily verify that [23, Theorem 2] and [21, Theorem 1.1] can be derived from (1) and (2) of Theorem 1.
Remark 3.
Our computer experiments seem to indicate that if is a permutation over , then it is necessary that . When , this is indeed the case and was recently proved in [22]. For a general , however, the method used there does not seem to work. We will come back to this question in the near future. If this “necessity property” were proved, then Theorem 1 indicates that is a permutation with uniform BCT if and only if , that is, the set completely charaterizes permutaitons with uniform BCT. This may be another reason why we would expect that [23, Theorem 2] and [21, Theorem 1.1] can be derived from (1) and (2) of Theorem 1.
Remark 4.
Finally, for two permutations and over , it is known that if or and are affine equivalent [6]; and if both and are quadratic and extended affine equivalent, then if [27]. We have checked that for , all the functions for are affine equivalent to the Gold function , which is known to be a permutation of with uniform BCT. It might be interesting to know if this holds for a general odd , or if there are permutations with uniform BCT which are not affinely equivalent to the Gold function. In Table 1 we list all known permutations over with for even .
No.  Reference  Remark  
1  [6]  odd  
2  [6]  odd,  
3  [20]  Equivalent to No. 2  
4  [27]    
5  [36]  Covered by No. 7  
6  [21, 23]  Covered by No. 7  
7  This paper  Equivalence unknown 
The rest of this paper is organized as follows: in Section 2 we collect some solvability criteria on certain equations over finite fields which will be used repeatedly in the paper; in Section 3 we present some identities and relations involving the ’s and ’s from the quarinomial ; in Section 4 we discuss in details the solvability of the difference equation ; in Section 5 which is the longest section of the paper, we prove the main result, dealing with Parts (1), (3) and (2) of Theorem 1 individually in three seperate subsections.
2 Preliminaries
The following three results will be used repeatedly in the rest of the paper.
Lemma 1.
([25]) Let be a positive integer. For any and , the equation
is solvable (with two solutions) in if and only if
Here is the absolute trace map from to the binary field .
Lemma 2.
([17]) Let be positive integers such that . For any , the equation
has either 0 or 2 solutions in . Moreover, it is solvable with two solutions in if and only if .
Lemma 3.
([23]) Let be odd integers such that . Let . For any , define
Denote by the number of solutions of in . Then . More precisely, let and be defined by the equations
Then

if and only if one of the following conditions is satisfied:
(i) and ;
(ii) , and . 
if and only if , , and .
If and , then the set of four solutions of in is given by .
3 Some identities
Before proceeding to the proof of the main result, in this section we collect some useful identities and relations which play important roles in the rest of the paper.
3.1 For
We first assume that , and the function is given in (1.2). Since and
we can find such that
(3.1) 
We fix such an element . It is known that
(3.2) 
Lemma 4.
If , then we have

;

;

;

;

;

.
Proof.
Identities (1)(5) can be verified by a routine computation. Only (6) requires some explanation.
3.2 For
Next we assume that . First, identity (6) of Lemma 4 becomes
Next, for any , define
(3.3) 
and
(3.4) 
Define (this is to avoid confusion which might result from using the more standard notation ). It is easy to see that
Define
(3.5) 
Lemma 5.
If , then for any , we have

;

for any .
Proof.
(1). Suppose for some . Obviously . Let be the unique element of satisfying . Thus , and we obtain
Letting , we have
(3.6) 
Since , we have , Lemma 1 implies that (3.6) is solvable with . From , we find , that is, , and hence . This clearly contradicts (3.6) since we know that .
(2). Let . We have
and
With some computation, we can obtain that
Using (6) of Lemma 4 and the properties of given in (3.1) and (3.2), we can verify that
This clearly shows that .
Similarly, by taking , one can also verify that . This completes the proof of (2). Now Lemma 5 is proved. ∎
Lemma 6.
If , then for any , we have the identity
(3.7) 
Comments
There are no comments yet.