Explore the vast range of titles available.

In this article we introduce a method of constructing binary linear codes and computing their weights by means of Boolean functions arising from mathematical objects called simplicial complexes. Inspired by Adamaszek (Am Math Mon 122:367–370, 2015) we introduce n-variable generating functions associated with simplicial complexes and derive explicit formulae. Applying the construction (Carlet in Finite Field Appl 13:121–135, 2007; Wadayama in Des Codes Cryptogr 23:23–33, 2001) of binary linear codes to Boolean functions arising from simplicial complexes, we obtain a class of optimal linear codes and a class of minimal linear codes.

One of the problems of modern discrete mathematics is Dedekind’s problem on the number of monotone Boolean functions. For other precomplete classes, general formulas for the number of functions of the classes had been found, but it has not been found so far for the class of monotone Boolean functions. Within the framework of this problem, there are problems of a lower level. One of them is the absence of a general formula for the number of Boolean functions of intersection of two classes—the class of monotone functions and the class of self-dual functions. In the paper, new lower bounds are proposed for estimating the cardinality of the intersection for both an even and an odd number of variables. It is shown that the majority voting function of an odd number of variables is monotone and self-dual. The majority voting function of an even number of variables is determined. Free voting functions, which are functions with fictitious variables similar in properties to majority voting functions, are introduced. Then the union of a set of majority voting functions and a set of free voting functions is considered, and the cardinality of this union is calculated. The resulting value of the cardinality is proposed as a lower bound for . For the class of monotone self-dual functions of an even number of variables, the lower bound is improved over the bounds proposed earlier, and for functions of an odd number of variables, the lower bound for is presented for the first time.

Boolean networks (BNs) are well-studied models of genomic regulation in biology where nodes are genes and their state transition is controlled by Boolean functions. We propose to learn Boolean functions as Boolean formulas in disjunctive normal form (DNFs) by an explainable neural network Mat_DNF and apply it to learning BNs. Directly expressing DNFs as a pair of binary matrices, we learn them using a single layer NN by minimizing a logically inspired non-negative cost function to zero. As a result, every parameter in the network has a clear meaning of representing a conjunction or literal in the learned DNF. Also we can prove that learning DNFs by the proposed approach is equivalent to inferring interpolants in logic between the positive and negative data. We applied our approach to learning three literature-curated BNs and confirmed its effectiveness. We also examine how generalization occurs when learning data is scarce. In doing so, we introduce two new operations that can improve accuracy, or equivalently generalizability for scarce data. The first one is to append a noise vector to the input learning vector. The second one is to continue learning even after learning error becomes zero. The first one is explainable by the second one. These two operations help us choose a learnable DNF, i.e., a root of the cost function, to achieve high generalizability.

The big APN problem is one of the most important challenges in the theory of Boolean functions, i.e. finding a new APN permutation in even dimension. Among this class of functions, those with the lowest possible degree are cubic. Yet, none has been found so far. In this paper, we introduce new parameters for Boolean functions and for vectorial Boolean functions, mostly derived from the behavior of their second-order derivatives. These parameters are invariant under extended affine equivalence, and they are particularly relevant for small-degree functions. They allow studying bent, semi-bent and APN functions of degrees two and three. In particular, they allow tackling the big APN problem for cubic permutations. Notably, we focus on the case of dimension 8, providing some computational results.

Given a convex function Φ:[0,1]→R and the mean Ef(X)=a∈[0,1], which Boolean function f maximizes the Φ-stability E[Φ(Tρf(X))] of f? Here X is a random vector uniformly distributed on the discrete cube -1,1n and Tρ is the Bonami–Beckner operator. Special cases of this problem include the (symmetric and asymmetric) α-stability problems and the “Most Informative Boolean Function” problem. In this paper, we provide several upper bounds for the maximal Φ-stability. When specializing Φ to some particular forms, by these upper bounds, we partially resolve Mossel and O’Donnell’s conjecture on α-stability with α>2, Li and Médard’s conjecture on α-stability with 1<α<2, and Courtade and Kumar’s conjecture on the “Most Informative Boolean Function” which corresponds to a conjecture on α-stability with α=1. Our proofs are based on discrete Fourier analysis, optimization theory, and improvements of the Friedgut–Kalai–Naor (FKN) theorem. Our improvements of the FKN theorem are sharp or asymptotically sharp for certain cases.

The construction and development of new techniques for a nonlinear multivalued Boolean function is one of the important aspects of modern ciphers. These multivalued Boolean functions need to be defined over various algebraic structures which map multiple inputs on multiple outputs. Modern block ciphers are a combination of linear and nonlinear functions which adds diffusion and confusion capabilities. We have offered an innovative system for the construction of the confusion component of block cipher by using recurrent neural networks. Since the confusion component is a multivalued Boolean function, therefore, we need many to many types of recurrent networks with an equal number of inputs and outputs. With this scheme, we have achieved a standard benchmark nonlinear of 112 with balancednesss having low linear and differential probabilities. We evaluated some common and advanced measures for the eminence of randomness and cryptanalytics to observe the efficiency of the proposed methodology. These outcomes validated the generated nonlinear confusion components are effective for block ciphers and have better cryptographic strength in image encryption with a high signal-to-noise ratio in comparison to state-of-the-art techniques.

The recent FLIP cipher is an encryption scheme described by Méaux et al. at the conference EUROCRYPT 2016. It is based on a new stream cipher model called the filter permutator and tries to minimize some parameters (including the multiplicative depth). In the filter permutator, the input to the Boolean function has constant Hamming weight equal to the weight of the secret key. As a consequence, Boolean functions satisfying good cryptographic criteria when restricted to the set of vectors with constant Hamming weight play an important role in the FLIP stream cipher. Carlet et al. have shown that for Boolean functions with restricted input, balancedness and nonlinearity parameters continue to play an important role with respect to the corresponding attacks on the framework of FLIP ciphers. In particular, Boolean functions which are uniformly distributed over F2 on En,k=x∈F2n∣wt(x)=k for every 0 < k < n are called weightwise perfectly balanced (WPB) functions, where wt(x) denotes the Hamming weight of x. In this paper, we firstly propose two methods of constructing weightwise perfectly balanced Boolean functions in 2k variables (where k is a positive integer) by modifying the support of linear and quadratic functions. Furthermore, we derive a construction of n-variable weightwise almost perfectly balanced Boolean functions for any positive integer n.

Almost perfect nonlinear (in brief, APN) functions are vectorial functions F : F 2 n → F 2 n playing roles in several domains of information protection, at the intersection of computer science and mathematics. Their definition comes from cryptography and is also related to coding theory. When they are used as substitution boxes (S-boxes, which are the only nonlinear components in block ciphers), APN functions contribute optimally to the resistance against differential attacks. This makes of course a strong cryptographic motivation for their study, which has been very active since the 90’s, and has posed interesting and difficult mathematical questions, some of which are still unanswered. Since the introduction of differential attacks, more recent types of cryptanalyses have been designed, such as integral attacks. No notion about S-boxes has been identified which would play a similar role with respect to integral attacks. In this paper, we study two generalizations of APNness that are natural from a mathematical point of view, since they directly extend classical characterizations of APN functions. We call these two notions strong non-normality and sum-freedom. The former existed already for Boolean functions (it had been introduced by Dobbertin), and the latter is new. We study how these two notions are related to cryptanalyses (the relation is weaker for strong non-normality). The two notions behave differently from each other, while they have similar definitions. They behave differently from differential uniformity, which is a well-known generalization of APNness. We study the different ways to define them. We prove their satisfiability, their monotonicity, and their invariance under classical equivalence relations, and we characterize them by the Walsh transform. We finally begin a study of the multiplicative inverse function (used as a substitution box in the Advanced Encryption Standard and other block ciphers) from the viewpoint of these two notions. In particular, we find a simple expression of the sum of the values taken by this function over affine subspaces of F 2 n that are not vector subspaces. This formula shows that the sum never vanishes on such affine spaces. We also give a formula for the case of a vector space defined by one of its bases.

The problem of bi-decomposition of a Boolean function is to represent a given Boolean function as a logic algebra operation over two Boolean functions. A method based on bi-decomposition of Boolean functions is suggested to implement systems of incompletely specified (partial) Boolean functions in the basis of two-input gates. This basis can be the basis of NOR gates, NAND gates or the basis of AND and OR gates with accessible input complements. The used method for bi-decomposition is reduced to the search for weighted two-block cover of a complete bipartite weighted graph with complete bipartite subgraphs (bi-cliques). The graph represents differences between the rows of Boolean matrices that specify the given system of partial Boolean functions. The system is given by two Boolean matrices, one of which represents the domain of Boolean space where the values of the given functions are specified, and the other—the values of the functions on the elements of the domain. Every bi-clique in the obtained cover is assigned in a certain way with а set of variables that are the arguments of the functions. This set is the weight of the bi-clique. Every one of those bi-cliques defines a Boolean function whose arguments are the variables assigned to it. The functions obtained in such a way constitute the required decomposition. The process of synthesis of a combinational circuit consists in successive application of bi-decomposition to the obtained functions. The method for two-block covering the orthogonality graph of rows of ternary matrices is described.

Boolean functions are mathematical objects used in diverse domains and have been actively researched for several decades already. One domain where Boolean functions play an important role is cryptography. There, the plethora of settings one should consider and cryptographic properties that need to be fulfilled makes the search for new Boolean functions still a very active domain. There are several options to construct appropriate Boolean functions: algebraic constructions, random search, and metaheuristics. In this work, we concentrate on metaheuristic approaches and examine the related works appearing in the last 25 years. To the best of our knowledge, this is the first survey work on this topic. Additionally, we provide a new taxonomy of related works and discuss the results obtained. Finally, we finish this survey with potential future research directions.