On equivalence between known families of quadratic APN functions

This paper is dedicated to a question whether the currently known families of quadratic APN polynomials are pairwise different up to CCZ-equivalence. We reduce the list of these families to those CCZ-inequivalent to each other. In particular, we prove that the families of APN trinomials (constructed by Budaghyan and Carlet in 2008) and multinomials (constructed by Bracken et al. 2008) are contained in the APN hexanomial family introduced by Budaghyan and Carlet in 2008. We also prove that a generalization of these trinomial and multinomial families given by Duan et al. (2014) is contained in the family of hexanomials as well.     

On equivalence between known polynomial APN functions and power APN functions

Constructions and equivalence of APN functions play a significant role in the research of cryptographic functions. On finite fields of characteristic 2, 6 families of power APN functions and 14 families of polynomial APN functions have been constructed in the literature. However, the study on the equivalence among the aforementioned APN functions is rather limited to the equivalence in the power APN functions. Meanwhile, the theoretical analysis on the equivalence between the polynomial APN functions and the power APN functions, as well as the equivalence in the polynomial APN functions themselves, is far less studied. In this paper, we give the theoretical analysis on the inequivalence in 8 known families of polynomial APN functions and power APN functions.     

A note on APN permutations in even dimension

APN permutations in even dimension are vectorial Boolean functions that play a special role in the design of block ciphers. We study their properties, providing some general results and some applications to the low-dimension cases. In particular, we prove that none of their components can be quadratic. For an APN vectorial Boolean function (in even dimension) with all cubic components we prove the existence of a component having a large number of balanced derivatives. Using these restrictions, we obtain the first theoretical proof of the non-existence of APN permutations in dimension 4. Moreover, we derive some constraints on APN permutations in dimension 6.     

Almost perfect nonlinear families which are not equivalent to permutations

An important problem on almost perfect nonlinear (APN) functions is the existence of APN permutations on even-degree extensions of ${\mathbb{F}}_2$ larger than 6. Browning et al. (2010) gave the first known example of an APN permutation on the degree-6 extension of ${\mathbb{F}}_2$. The APN permutation is CCZ-equivalent to the previously known quadratic Kim κ-function (Browning et al. (2009)). Aside from the computer based CCZ-inequivalence results on known APN functions on even-degree extensions of ${\mathbb{F}}_2$ with extension degrees less than 12, no theoretical CCZ-inequivalence result on infinite families is known. In this paper, we show that Gold and Kasami APN functions are not CCZ-equivalent to permutations on infinitely many even-degree extensions of ${\mathbb{F}}_2$. In the Gold case, we show that Gold APN functions are not equivalent to permutations on any even-degree extension of ${\mathbb{F}}_2$, whereas in the Kasami case we are able to prove inequivalence results for every doubly-even-degree extension of ${\mathbb{F}}_2$.     

APN permutations on and Costas arrays

We study PN and APN functions over the integers modulo n. We give some construction techniques based on Costas arrays, which allow us to construct APN permutations on where p is a prime. Although PN permutations do not exist, one set of our functions is very close to being a set of PN permutations.     

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.     

Enumerating cycles in the graph of overlapping permutations

The graph of overlapping permutations is a directed graph that is an analogue to the De Bruijn graph. It consists of vertices that are permutations of length $n$ and edges that are permutations of length $n+1$ in which an edge $a_1?a_{n+1}$ would connect the standardization of $a_1?a_n$ to the standardization of $a_2?a_{n+1}$. We examine properties of this graph to determine where directed cycles can exist, to count the number of directed $2$-cycles within the graph, and to enumerate the vertices that are contained within closed walks and directed cycles of more general lengths.     

A note on the total number of cycles of even and odd permutations

We prove bijectively that the total number of cycles of all even permutations of [n]={1,2,…,n} and the total number of cycles of all odd permutations of [n] differ by (−1)ⁿ(n−2)!, which was stated as an open problem by Miklós Bóna. We also prove bijectively the following more general identity:

     

A note on applications of the martingale central limit theorem to random permutations

A unified martingale approach is presented for establishing the asymptotic normality of some sequences of random variables. It is applied to the numbers of inversions, rises, and peaks, respectively, as well as the oscillation and the sum of consecutive pair products of a random permutation. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 323–332 (1997)     

Spectrum of certain tridiagonal matrices when their dimension goes to infinity

This paper deals with the spectra of matrices similar to infinite tridiagonal Toeplitz matrices with perturbations and with positive off-diagonal elements. We will discuss the asymptotic behavior of the spectrum of such matrices and we use them to determine the values of a matrix function, for an entire function. In particular we determine the matrix powers and matrix exponentials.     

A family of crooked functions

It has been proved in Bierbrauer and Kyureghyan (Des. Codes Cryptogr. 46:269–301, 2008) that a binomial function aX ⁱ  + bX ^j can be crooked only if both exponents i, j have 2-weight  ≤2. In the present paper we give a brief construction for all known examples of crooked binomial functions. These consist of an infinite family and one sporadic example. The construction of the sporadic example uses the properties of an algebraic curve of genus 3. Computer experiments support the conjecture that each crooked binomial is equivalent either to a member of the family or to the sporadic example.      

A new approach to the representation of trigonometric and hyperbolic functions by infinite products

An innovative technique is developed for obtaining infinite product representations for some elementary functions. The technique is based on the comparison of alternative expressions of Green's functions constructed by two different methods. Some standard boundary value problems are considered posed for two-dimensional Laplace equation on regions of a regular configuration. Classical closed analytic form of Green's functions for such problems are compared against those obtained by the method of images in the form of infinite products. This yields a number of new infinite product representations for trigonometric and hyperbolic functions.     

On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions

Evolutionary algorithms are randomized search heuristics, which are often used as function optimizers. In this paper the well-known (1+1) Evolutionary Algorithm ((1+1) EA) and its multistart variants are studied. Several results on the expected runtime of the (1+1) EA on linear or unimodal functions have already been presented by other authors. This paper is focused on quadratic pseudo-boolean functions, i.e., polynomials of degree 2, a class of functions containing NP-hard optimization problems. Subclasses of the class of all quadratic functions are identified where the (1+1) EA is efficient, for other subclasses the (1+1) EA has exponential expected runtime, but a large enough success probability within polynomial time such that a multistart variant of the (1+1) EA is efficient. Finally, a particular quadratic function is identified where the EA and its multistart variants fail in polynomial time with overwhelming probability.     

A Boolean measure of similarity

We propose a way of measuring the similarity of a Boolean vector to a given set of Boolean vectors, motivated in part by certain data mining or machine learning problems. We relate the similarity measure to one based on Hamming distance and we develop from this some ways of quantifying the ‘quality’ of a dataset.     

Counting occurrences of 231 in an involution

We study the generating function for the number of involutions on n letters containing exactly r?0 occurrences of 231. It is shown that finding this function for a given r amounts to a routine check of all involutions of length at most 2r+2.     

On the probability of union in the n-space

In this paper, our sets are orthants in $R^n$ and $N$, the number of them, is large ($N>n$). We introduce the modified inclusion–exclusion formula in order to efficiently calculate the probability of a union of such events. The new formula works in the bivariate case, and can also be used in $R^n,n\ge 3$ with a condition on the projected sets onto lower dimensional spaces. Numerical examples are presented.