Rotation symmetric Boolean functions—Count and cryptographic properties

Rotation symmetric (RotS) Boolean functions have been used as components of different cryptosystems. This class of Boolean functions are invariant under circular translation of indices. Using Burnside's lemma it can be seen that the number of n-variable rotation symmetric Boolean functions is 2^g_n, where g_n=(1/n)∑_t|nφ(t)2^n/t, and φ(.) is the Euler phi-function. In this paper, we find the number of short and long cycles of elements in having fixed weight, under the RotS action. As a consequence we obtain the number of homogeneous RotS functions having algebraic degree w. Our results make the search space of RotS functions much reduced and we successfully analyzed important cryptographic properties of such functions by executing computer programs. We study RotS bent functions up to 10 variables and observe (experimentally) that there is no homogeneous rotation symmetric bent function having degree >2. Further, we studied the RotS functions on 5,6,7 variables by computer search for correlation immunity and propagation characteristics and found some functions with very good cryptographic properties which were not known earlier.     

Boolean functions with MacWilliams duality

We introduce a new class of Boolean functions for which the MacWilliams duality holds, called MacWilliams-dual functions, by considering a dual notion on Boolean functions. By using the MacWilliams duality, we prove the Gleason-type theorem on MacWilliams-dual functions. We show that a collection of MacWilliams-dual functions contains all the bent functions and all formally self-dual functions. We also obtain the Pless power moments for MacWilliams-dual functions. Furthermore, as an application, we prove the nonexistence of bent functions in 2n variables with minimum degree n?k for any nonnegative integer k and n ≥ N with some positive integer N under a certain condition.     

Piecewise Constructions of Bent and Almost Optimal Boolean Functions

The first aim of this work was to generalize the techniques used in MacWilliams’ and Sloane’s presentation of the Kerdock code and develop a theory of piecewise quadratic Boolean functions. This generalization led us to construct large families of potentially new bent and almost optimal functions from quadratic forms in this piecewise fashion. We show how our motivating example, the Kerdock code, fits into this setting. These constructions were further generalized to non-quadratic bent functions. The resulting constructions design n-variable bent (resp. almost optimal) functions from n-variable bent or almost optimal functions. Communicated by: T. Helleseth     

CCZ-equivalence of bent vectorial functions and related constructions

We observe that the CCZ-equivalence of bent vectorial functions over ${{\bf F}_2^n}$ (n even) reduces to their EA-equivalence. Then we show that in spite of this fact, CCZ-equivalence can be used for constructing bent functions which are new up to EA-equivalence and therefore to CCZ-equivalence: applying CCZ-equivalence to a non-bent vectorial function F which has some bent components, we get a function F?? which also has some bent components and whose bent components are CCZ-inequivalent to the components of the original function F. Using this approach we construct classes of nonquadratic bent Boolean and bent vectorial functions.     

On second-order nonlinearity and maximum algebraic immunity of some bent functions in \mathcal{PS}^{+}

The rth-order nonlinearity and algebraic immunity of Boolean function play a central role against several known attacks on stream and block ciphers. Since its maximum equals the covering radius of the rth-order Reed-Muller code, it also plays an important role in coding theory. The computation of exact value or high lower bound on the rth-order nonlinearity of a Boolean function is very complected/challenging problem, especially when r>1. In this article, we identify a subclass of \({\mathcal{D}}_{0}\) type bent functions constructed by modifying well known Dillon functions having sharper bound on their second-order nonlinearity. We further, identify a subclass of bent functions in \({\mathcal {PS}}^{+}\) class with maximum possible algebraic immunity. The result is proved by using the well known conjecture proposed by Tu and Deng (Des. Codes Cryptogr. 60(1):1–14, 2011). To obtain rth-order nonlinearity (r>2), that is, whole nonlinearity profile of the constructed bent functions is still an open problem.     

Construction of balanced Boolean functions with high nonlinearity and good autocorrelation properties

Boolean functions with high nonlinearity and good autocorrelation properties play an important role in the design of block ciphers and stream ciphers. In this paper, we give a method to construct balanced Boolean functions of n variables, where n ≥ 10 is an even integer, satisfying strict avalanche criterion (SAC), and with high algebraic degree. Compared with the known balanced Boolean functions with SAC property, the constructed functions possess the highest nonlinearity and the best global avalanche characteristics property.     

Normal Boolean functions

Dobbertin (Construction of bent functions and balanced Boolean functions with high nonlinearity, in: Fast Software Encryption, Lecture Notes in Computer Science, Vol. 1008, Springer, Berlin, 1994, pp. 61–74) introduced the normality of bent functions. His work strengthened the interest for the study of the restrictions of Boolean functions on k-dimensional flats providing the concept of k-normality. Using recent results on the decomposition of any Boolean functions with respect to some subspace, we present several formulations of k-normality. We later focus on some highly linear functions, bent functions and almost optimal functions. We point out that normality is a property for which these two classes are strongly connected. We propose several improvements for checking normality, again based on specific decompositions introduced in Canteaut et al. (IEEE Trans. Inform. Theory, 47(4) (2001) 1494), Canteaut and Charpin (IEEE Trans. Inform. Theory). As an illustration, we show that cubic bent functions of 8 variables are normal.     

Duality between bent functions and affine functions

A Boolean function in an even number of variables is called bent if it is at the maximal possible Hamming distance from the class of all affine Boolean functions. We prove that there is a duality between bent functions and affine functions. Namely, we show that affine function can be defined as a Boolean function that is at the maximal possible distance from the set of all bent functions.     

Refined estimates of the number of repetition-free boolean functions in the full binary basis {&, ∨, ⊕, −

We consider repetition-free Boolean functions in the basis {&, ∨, ⊕, ?}, and prove a formula expressing the number of such functions of n variables as a product of Fibonacci numbers. These products are estimated; as a result, we obtain asymptotic estimates for the number of repetition-free Boolean functions. These estimates involve Euler numbers of second order and can be reduced by well-known methods to the form of an exponential-power series. These estimates can be used to construct the final asymptotics of the number of repetition-free Boolean functions in the full binary basis.     

Binary linear codes with few weights from Boolean functions

Boolean functions have very nice applications in coding theory and cryptography. In coding theory, Boolean functions have been used to construct linear codes in different ways. The objective of this paper is to construct binary linear codes with few weights using the defining-set approach. The defining sets of the codes presented in this paper are defined by some special Boolean functions and some additional restrictions. First, two families of binary linear codes with at most three or four weights from Boolean functions with at most three Walsh transform values are constructed and the parameters of their duals are also determined. Then several classes of binary linear codes with explicit weight enumerators are produced. Some of the binary linear codes are optimal or almost optimal according to the tables of best codes known maintained at http://www.codetables.de, and the duals of some of them are distance-optimal with respect to the sphere packing bound.

     

Sur le critère de propagation de degré ℓ et d'ordre k

We determine the Boolean functions on GF(2)ⁿ which satisfy the propagation criterion of degree ℓ and order k ≥ n - ℓ - 2. All of theses functions are quadratic. We design nonquadratic Boolean functions satisfying the criterion PC(ℓ) of order k by using the Maiorana-McFarland construction involving nonlinear mappings derived from nonlinear codes.     

Partial difference sets and amorphic group schemes from pseudo-quadratic bent functions

We present new abelian partial difference sets and amorphic group schemes of both Latin square type and negative Latin square type in certain abelian p-groups. Our method is to construct what we call pseudo-quadratic bent functions and use them in place of quadratic forms. We also discuss a connection between strongly regular bent functions and amorphic group schemes.     

The essential dependence of Kasami bent functions on the products of variables

Kasami bent functions have the most complicated properties in the class of algebraic constructions of bent functions. We prove that the degree t Kasami functions have nonzero order t ? 2 derivatives for 4 ≤ t ≤ (n + 3)/3 and nonzero order t ? 3 derivatives for (n + 3)/3 < t ≤ n/2. We establish that the order of essential dependence of Kasami bent functions equals either t ? 2 or t ? 3.     

The Higher Spin Laplace Operator

This paper deals with a certain class of second-order conformally invariant operators acting on functions taking values in particular (finite-dimensional) irreducible representations of the orthogonal group. These operators can be seen as a generalisation of the Laplace operator to higher spin as well as a second-order analogue of the Rarita-Schwinger operator. To construct these operators, we will use the framework of Clifford analysis, a multivariate function theory in which arbitrary irreducible representations for the orthogonal group can be realised in terms of polynomials satisfying a system of differential equations. As a consequence, the functions on which this particular class of operators act are functions taking values in the space of harmonics homogeneous of degree k. We prove the ellipticity of these operators and use this to investigate their kernel, focusing on polynomial solutions. Finally, we will also construct the fundamental solution using the theory of Riesz potentials.     

On the notion of canonical dimension for algebraic groups

We define and study a numerical invariant of an algebraic group action which we call the canonical dimension. We then apply the resulting theory to the problem of computing the minimal number of parameters required to define a generic hypersurface of degree d in P^n-1.     

A novel algorithm enumerating bent functions

Based on the relationship between the Walsh spectra of a Boolean function at partial points and the Walsh spectra of its subfunctions, and on the binary Möbius transform, a novel algorithm is developed, which can theoretically construct all bent functions. Practically we enumerate all bent functions in 6 variables. With the restriction on the algebraic normal form, the algorithm is also efficient in more variables case. For example, enumeration of all homogeneous bent functions of degree 3 in 8 variables can be done in one minute with a P4 1.7 GHz computer; the nonexistence of homogeneous bent functions in 10 variables of degree 4 is computationally proved.     

Finding nonnormal bent functions

The question if there exist nonnormal bent functions was an open question for several years. A Boolean function in n variables is called normal if there exists an affine subspace of dimension n/2 on which the function is constant. In this paper we give the first nonnormal bent function and even an example for a nonweakly normal bent function. These examples belong to a class of bent functions found in [J.F. Dillon, H. Dobbertin, New cyclic difference sets with Singer parameters, in: Finite Fields and Applications, to appear], namely the Kasami functions. We furthermore give a construction which extends these examples to higher dimensions. Additionally, we present a very efficient algorithm that was used to verify the nonnormality of these functions.     

Chiral equivariant cohomology I

We construct a new equivariant cohomology theory for a certain class of differential vertex algebras, which we call the chiral equivariant cohomology. A principal example of a differential vertex algebra in this class is the chiral de Rham complex of Malikov-Schechtman-Vaintrob of a manifold with a group action. The main idea in this paper is to synthesize the algebraic approach to classical equivariant cohomology due to H. Cartan,² with the theory of differential vertex algebras, by using an appropriate notion of invariant theory. We also construct the vertex algebra analogues of the Mathai-Quillen isomorphism, the Weil and the Cartan models for equivariant cohomology, and the Chern-Weil map. We give interesting cohomology classes in the new theory that have no classical analogues.     

Non-Archimedean White Noise,Pseudodifferential Stochastic Equations,and Massive Euclidean Fields

We construct p-adic Euclidean random fields \(\varvec{\Phi }\) over \(\mathbb {Q}_{p}^{N}\), for arbitrary N, these fields are solutions of p-adic stochastic pseudodifferential equations. From a mathematical perspective, the Euclidean fields are generalized stochastic processes parametrized by functions belonging to a nuclear countably Hilbert space, these spaces are introduced in this article, in addition, the Euclidean fields are invariant under the action of certain group of transformations. We also study the Schwinger functions of \(\varvec{\Phi }\).