Rychkov, K. L.
Published in
Journal of Applied and Industrial Mathematics

We prove that, for n equal to 3, 5, and a power of 2, every minimal partition of the edge set of the n-dimensional cube is perfect. As a consequence, we obtain some description of the classes of all minimal parallel-serial contact schemes (π-schemes) realizing the linear Boolean functions that depend essentially on n variables for the corresponding...

Voronenko, A. A. Karchmit, I. A.
Published in
Moscow University Computational Mathematics and Cybernetics

New upper bound 3n is presented for the cardinality of the definition domain of a universal function for a class of linear Boolean functions in which n is the number of variables.

Charpin, Pascale

Crooked permutations were defined twenty years ago. It was firstly shown that they can be used to construct interesting objects in graph theory. The field of applications was extended later, since crooked functions, bijective or not, correspond to APN functions and to some optimal codes. We adopt an unified presentation, of crooked functions, expla...

Canteaut, Anne Perrin, Léo Tian, Shizhu

Whether there exist Almost Perfect Non-linear permutations (APN) operating on an even number of bit is the so-called Big APN Problem. It has been solved in the 6-bit case by Dillon et al. in 2009 but, since then, the general case has remained an open problem. In 2016, Perrin et al. discovered the butterfly structure which contains Dillon et al.'s p...

Beierle, Christof Biryukov, Alex Udovenko, Aleksei

A set ⊆ 2 is called degree-d zero-sum if the sum ∑ ∈ ( ) vanishes for all n-bit Boolean functions of algebraic degree at most d. Those sets correspond to the supports of the n-bit Boolean functions of degree at most n − d − 1. We prove some results on the existence of degree-d zero-sum sets of full rank, i.e., those that contain n linearly independ...

Charpin, Pascale

Crooked permutations were introduced twenty years ago since they allow to construct interesting objects in graph theory. The field of applications was extended later. Crooked functions, bijective or not, correspond to APN functions and to some optimal codes. We adopt an unified presentation of crooked functions, explaining the connection with parti...

Charpin, Pascale

Crooked permutations were introduced twenty years ago to cons- truct interesting objects in graph theory. These functions, over F2n with odd $n$, are such that their derivatives have as image set a com- plement of a hyperplane. The field of applications was extended later, in particular to cryptography. However binary crooked functions are rare. It...

Redkin, Nikolay P.
Published in
Discrete Mathematics and Applications

We study generalized (in terms of bases) complexity of implementation of linear Boolean functions by Boolean circuits in arbitrary functionally complete bases; the complexity of a circuit is defined as the number of gates. Let L*(n) be the minimal number of gates sufficient for implementation of an arbitrary linear Boolean function of n variables i...

Couceiro, Miguel Lehtonen, Erkko Mercuriali, Pierre Péchoux, Romain

A normal form system (NFS) for representing Boolean functions is thought of as a set of stratified terms over a fixed set of connectives. For a fixed NFS A, the complexity of a Boolean function f with respect to A is the minimum of the sizes of terms in A that represent f. This induces a preordering of NFSs: an NFS A is polynomially as efficient as...

Logachev, Oleg A. Fedorov, Sergey N. Yashchenko, Valerii V.
Published in
Discrete Mathematics and Applications

A new equivalence relation on the set of Boolean functions is introduced: functions are declared to be Δ-equivalent if their autocorrelation functions are equal. It turns out that this classification agrees well with the cryptographic properties of Boolean functions: for functions belonging to the same Δ-equivalence class a number of their cryptogr...