New differentially 4-uniform permutations from modifications of the inverse function

Finding permutations with good cryptographic parameters is a good research topic about constructing a secure S-box in substitution-permutation networks. In particular constructing differentially 4-uniform permutations has made considerable progress in recent years. In this paper, we present new differentially 4-uniform permutations from the inverse function composed by disjoint cycles. Our new differentially 4-uniform permutations have high nonlinearity and low differential-linear uniformity. We give the differential spectrum and the extended Walsh spectrum of some of our differentially 4-uniform permutations, and then we can see that they are CCZ-inequivalent to some permutations whose differential spectrum and extended Walsh spectrum are known.     

On the boomerang uniformity of permutations of low Carlitz rank

Finding permutation polynomials with low differential and boomerang uniformity is an important topic in S-box designs of many block ciphers. For example, AES chooses the inverse function as its S-box, which is differentially 4-uniform and boomerang 6-uniform. Also there has been considerable research on many non-quadratic permutations which are modifications of the inverse function. In this paper, we give a novel approach which shows that plenty of existing modifications of the inverse function are in fact affine equivalent to permutations of low Carlitz rank, and those modifications cannot be APN. We also present the complete list of permutations of Carlitz rank 3 having the boomerang uniformity six, and give the complete classification of the differential uniformities of permutations of Carlitz rank 3. As an application, we provide all the involutions of Carlitz rank 3 having the boomerang uniformity six.     

A negative answer to Bracken–Tan–Tan's problem on differentially 4-uniform permutations over F2n

Permutations with low differential uniformity are widely used in cipher design. Recently, Bracken, Tan and Tan (2012) [5] presented a method to construct differentially 4-uniform permutations by changing certain conditions of known APN functions. They guessed that only two classes of existing quadratic APN functions have this property. They succeeded in proving one class and left the other one as an open problem. In this paper, with the help of a computer, those polynomials are proved to be differentially 4-uniform but may not be permutation polynomials, which give a negative answer to this problem.     

A new family of differentially 4-uniform permutations over $$\mathbb{F}_{2^{2k} }$$ for odd k

We study the differential uniformity of a class of permutations over \(\mathbb{F}_{2^n } \) with n even. These permutations are different from the inverse function as the values x^?1 are modified to be (γx)^? on some cosets of a fixed subgroup 〈γ〉 of \(\mathbb{F}_{2^n }^* \). We obtain some sufficient conditions for this kind of permutations to be differentially 4-uniform, which enable us to construct a new family of differentially 4-uniform permutations that contains many new Carlet-Charpin-Zinoviev equivalent (CCZ-equivalent) classes as checked by Magma for small numbers n. Moreover, all of the newly constructed functions are proved to possess optimal algebraic degree and relatively high nonlinearity.     

Further results on differentially 4-uniform permutations over F_(2~2m)

We present several new constructions of differentially 4-uniform permutations over F22 mby modifying the values of the inverse function on some subsets of F22 m. The resulted differentially 4-uniform permutations have high nonlinearities and algebraic degrees, which provide more choices for the design of crytographic substitution boxes.     

Constructing new differentially 4-uniform permutations from known ones

In this paper we study a new construction of differentially 4-uniform permutations from known ones and the inverse function. We focus on constructing methods of [20]. We split a finite field into its subfield and remainder, and, we choose known differentially 4-uniform permutations over the subfield and the inverse function over the entire field. As a result, we obtain two families of differentially 4-uniform permutations.     

The design of composite permutations with applications to DES-like S-boxes

This paper presents an iterative construction method for building composite permutations. Its efficiency is based on the concepts of pre-computation and equivalence classes. Equivalence class representatives of permutations on four bits are pre-computed. These class representatives can serve as input to the construction method, however, the results are also of independent interest for applications in cryptography. A well-known example of a cryptosystem using composite permutations for its Substitution boxes (S-boxes) is the Data Encryption Standard (DES). Throughout the paper, DES-like S-boxes are defined as mappings satisfying all design criteria as disclosed by one of the designers of DES. All permutations on four bits with DES-like properties are identified. Starting with pre-computed representatives of classes with such permutations, two iterations of a specialized version of the algorithm are applied to obtain bounds on the minimum differential uniformity and minimum non-linear uniformity of DES-like S-boxes. It is established that the two values cannot be less than eight, and that DES-like S-boxes for which the values are both equal to 12 do exist. In addition, if the non-linear uniformity of each of the four permutations in a DES-like S-box is at most six, as in all DES S-boxes, then its non-linear uniformity cannot be less than ten and its minimum differential uniformity equals 12.     

Investigations of c-differential uniformity of permutations with Carlitz rank 3

The c-differential uniformity is recently proposed to reflect resistance against some variants of differential attack. Finding functions with low c-differential uniformity is attracting attention from many researchers. For even characteristic, it is known that permutations of low Carlitz rank have good cryptographic parameters, for example, low differential uniformity, high nonlinearity, etc. In this paper we show that permutations with low Carlitz rank have low c-differential uniformity. We also investigate c-differential uniformity of permutations with Carlitz rank 3 in detail.     

More constructions of APN and differentially 4-uniform functions by concatenation

We study further the method of concatenating the outputs of two functions for designing an APN or a differentially 4-uniform (n, n)-function for every even n. We deduce several specific constructions of APN or differentially 4-uniform (n, n)-functions from APN and differentially 4-uniform (n/2, n/2)-functions. We also give a construction of quadratic APN functions which includes as particular cases a previous construction by the author and a more recent construction by Pott and Zhou.     

On the differential uniformities of functions over finite fields

In this paper, the possible value of the differential uniformity of a function over finite fields is discussed. It is proved that, the differential uniformity of a function over Fq can be any even integer between 2 and q when q is even; and it can be any integer between 1 and q except q-1 when q is odd. Moreover, for any possible differential uniformity t, an explicit construction of a differentially t-uniform function is given.     

Constructing new differentially 4-uniform permutations from the inverse function

Two new families of differentially 4-uniform permutations over ${\mathbb{F}}_{2^{2m}}$ are constructed by modifying the values of the inverse function on some subfield of ${\mathbb{F}}_{2^{2m}}$ and by applying affine transformations on the function. The resulted 4-uniform permutations have high nonlinearity and algebraic degree. A family of differentially 6-uniform permutations with high nonlinearity and algebraic degree is also constructed by making the modification on an affine subspace of ${\mathbb{F}}_{2^{2m}}$.     

Some highly symmetric authentication perpendicular arrays

A set S of permutations of k objects is -uniform, t-homogeneous if for every pair A, B of t-subsets of the ground set, there are exactly permutations in S mapping A onto B. Arithmetical conditions and symmetries are discussed. We describe the character-theoretic method which is useful if S is contained in a permutation group. A main result is the construction of a 2-uniform, 2-homogeneous set of permutations on 6 objects and of a 3-uniform, 3-homogeneous set of permutations on 9 objects. These are contained in the simple permutation groups PSL ₂(5) and PSL ₂(8), respectively. The result is useful in the framework of theoretical secrecy and authentication (see Stinson 1990, Bierbrauer and Tran 1991).     

On non-monomial APcN permutations over finite fields of even characteristic

Recently, a new concept called the c-differential uniformity was proposed by Ellingsen et al. (2020), which generalizes the notion of differential uniformity measuring the resistance against differential cryptanalysis. Since then, finding functions having low c-differential uniformity has attracted the attention of many researchers. However it seems that, at this moment, there are not many non-monomial permutations having low c-differential uniformity. In this paper, we present new classes of (almost) perfect c-nonlinear non-monomial permutations over a binary field.     

Convergence of Three-Step Taylor Galerkin Finite Element Scheme Based Monotone Schwarz Iterative Method for Singularly Perturbed Differential-Difference Equation

Monotone Schwarz iterative methods for parabolic partial differential equations are well known for their advantage of eliminating the search for an initial solution. In this article, we propose a monotone Schwarz iterative method for singularly perturbed parabolic retarded differential-difference equations based on a three-step Taylor Galerkin finite element scheme. The stability and ε-uniform convergence of the three-step Taylor Galerkin finite element method have been discussed. Further, by using maximum principle and induction hypothesis, the convergence of the proposed monotone Schwarz iterative method has been established.     

Constructing differentially 4-uniform permutations over GF(22m ) from quadratic APN permutations over GF(22m+1)

In this paper, by means of the idea proposed by Carlet (ACISP 1-15, 2011), differentially 4-uniform permutations with the best known nonlinearity over \({\mathbb{F}_{2^{2m}}}\) are constructed using quadratic APN permutations over \({\mathbb{F}_{2^{2m+1}}}\) . Special constructions are given using the Gold functions. The algebraic degree of the constructions and their compositional inverses is also investigated. One construction and its compositional inverse both have algebraic degree m + 1 over \({\mathbb{F}_2^{2m}}\) .     

Gowers $$U_3$$ norm of some classes of bent Boolean functions

The Gowers \(U_3\) norm of a Boolean function is a measure of its resistance to quadratic approximations. It is known that smaller the Gowers \(U_3\) norm for a Boolean function larger is its resistance to quadratic approximations. Here, we compute Gowers \(U_3\) norms for some classes of Maiorana–McFarland bent functions. In particular, we explicitly determine the value of the Gowers \(U_3\) norm of Maiorana–McFarland bent functions obtained by using APN permutations. We prove that this value is always smaller than the Gowers \(U_3\) norms of Maiorana–McFarland bent functions obtained by using differentially \(\delta \)-uniform permutations, for all \(\delta \ge 4\). We also compute the Gowers \(U_3\) norms for a class of cubic monomial functions, not necessarily bent, and show that for \(n=6\), these norm values are less than that of Maiorana–McFarland bent functions. Further, we computationally show that there exist 6-variable functions in this class which are not bent but achieve the maximum second-order nonlinearity for 6 variables.     

Bundles, presemifields and nonlinear functions

Bundles are equivalence classes of functions derived from equivalence classes of transversals. They preserve measures of resistance to differential and linear cryptanalysis. For functions over GF(2 ⁿ ), affine bundles coincide with EA-equivalence classes. From equivalence classes (“bundles”) of presemifields of order p ⁿ , we derive bundles of functions over GF(p ⁿ ) of the form λ(x)*ρ(x), where λ, ρ are linearised permutation polynomials and * is a presemifield multiplication. We prove there are exactly p bundles of presemifields of order p ² and give a representative of each. We compute all bundles of presemifields of orders p ⁿ ≤ 27 and in the isotopism class of GF(32) and we measure the differential uniformity of the derived λ(x)*ρ(x). This technique produces functions with low differential uniformity, including PN functions (p odd), and quadratic APN and differentially 4-uniform functions (p = 2).     

Gray code for derangements

We give a Gray code and constant average time generating algorithm for derangements, i.e., permutations with no fixed points. In our Gray code, each derangement is transformed into its successor either via one or two transpositions or a rotation of three elements. We generalize these results to permutations with number of fixed points bounded between two constants.     

Comparing Algorithms for Sorting with <Emphasis Type="Italic">t</Emphasis> Stacks in Series

We show that the left-greedy algorithm is a better algorithm than the right-greedy algorithm for sorting permutations using t stacks in series when t > 1. We also supply a method for constructing some permutations that can be sorted by t stacks in series and from this get a lower bound on the number of permutations of length n that are sortable by t stacks in series. Finally we show that the left-greedy algorithm is neither optimal nor defines a closed class of permutations for t > 2.AMS Subject Classification: 05A05, 68R05, 68W01.