The problem of counting all inequivalent monotone Boolean functions of nine variables is considered. We solve the problem using known algorithms and deriving new ones when necessary. We describe ...methods to count fixed points in sets of all monotone Boolean functions under a given permutation of input variables. With these techniques as a basis, we tabulate the cardinalities of these sets for nine variables. By applying Burnside's lemma and the numbers obtained, we calculate the number of inequivalent monotone Boolean functions of 9 variables, which equals 789,204,635,842,035,040,527,740,846,300,252,680.
We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise ...structure of the codes, our method exploits code symmetry. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In other words, we show that symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed-Muller codes with increasing block length and converging rate achieves capacity. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to all affine-invariant codes and, thus, to extended primitive narrow-sense BCH codes. This also resolves, in the affirmative, the existence question for capacity-achieving sequences of binary cyclic codes. The primary tools used in the proof are the sharp threshold property for symmetric monotone Boolean functions and the area theorem for extrinsic information transfer functions.
Weightwise degree-d functions are Boolean functions that take the values of a function of degree at most d on each set of fixed Hamming weight. The class of weightwise affine functions encompasses ...both the symmetric functions and the Hidden Weight Bit Function (HWBF). The good cryptographic properties of the HWBF, except for the nonlinearity, motivate to investigate a larger class with functions that share the good properties and have a better nonlinearity. Additionally, the homomorphic friendliness of symmetric functions exhibited in the context of hybrid homomorphic encryption and the recent results on homomorphic evaluation of Boolean functions make this class of functions appealing for efficient privacy-preserving protocols.
In this article we realize the first study on weightwise degree-d functions, focusing on weightwise affine and weightwise quadratic functions. We show some properties on these new classes of functions, in particular on the subclass of cyclic weightwise functions. We provide balanced constructions and prove nonlinearity lower bounds for all cyclic weightwise affine functions and for a family of weightwise quadratic functions. We complement our work with experimental results, they show that other cyclic weightwise linear functions than the HWBF have better cryptographic parameters, and considering weightwise quadratic functions allows to reach higher algebraic immunity and substantially better nonlinearity.
This paper provides a classification of all monotonic bipartite simple games. The problem we deal with is very versatile since simple games are inequivalent monotonic Boolean functions, functions ...that are used in many fields such as game theory, neural networks, artificial intelligence, reliability or multiple-criteria decision-making. The obtained classification can be implemented in an algorithm able to enumerate bipartite simple games. These numbers provide some light on enumerations of several subclasses of bipartite simple games, for which we find formulas.
Complete simple games, a subclass of all simple games for which the desirability relation is a complete preordering, were already classified by means of two parameters: a vector and a matrix fulfilling some conditions. Complete simple games are inequivalent monotonic regular Boolean functions. In this paper, we deduce a procedure for bipartite non-complete games, which allows enumerating the number of bipartite simple games. Several formulas are obtained, in particular polynomial expressions for the number of bicameral meet games and the number of bicameral join games, two types of voting systems widely used in practice.
In this paper, we make a comprehensive study of two classes of Boolean functions whose interest originally comes from hybrid symmetric-FHE encryption (with stream ciphers like FiLIP), but which also ...present much interest for general stream ciphers. The functions in these two classes are cheap and easy to implement, and they allow the resistance to all classical attacks and to their guess and determine variants as well. We determine exactly all the main cryptographic parameters (algebraic degree, resiliency order, nonlinearity, algebraic immunity) for all functions in these two classes, and we give close bounds for the others (fast algebraic immunity, the dimension of the space of annihilators of minimal degree). This is the first time that this is done for all functions in large classes of cryptographic interest.
This paper is to design substitution boxes (S-Boxes) using innovative I-Ching operators (ICOs) that have evolved from ancient Chinese I-Ching philosophy. These three operators-intrication, turnover, ...and mutual- inherited from I-Ching are specifically designed to generate S-Boxes in cryptography. In order to analyze these three operators, identity, compositionality, and periodicity measures are developed. All three operators are only applied to change the output positions of Boolean functions. Therefore, the bijection property of S-Box is satisfied automatically. It means that our approach can avoid singular values, which is very important to generate S-Boxes. Based on the periodicity property of the ICOs, a new network is constructed, thus to be applied in the algorithm for designing S-Boxes. To examine the efficiency of our proposed approach, some commonly used criteria are adopted, such as nonlinearity, strict avalanche criterion, differential approximation probability, and linear approximation probability. The comparison results show that S-Boxes designed by applying ICOs have a higher security and better performance compared with other schemes. Furthermore, the proposed approach can also be used to other practice problems in a similar way.
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.
A convex continuation of an arbitrary Boolean function to the set is constructed. Moreover, it is proved that for any Boolean function that has no neighboring points on the set , the constructed ...function is the only totally maximally convex continuation to . Based on this, in particular, it is constructively stated that the problem of solving an arbitrary system of Boolean equations can be reduced to the problem of minimizing a function any local minimum of which in the desired region is a global minimum, and thus for this problem the problem of local minima is completely resolved.
Complete complementary codes (CCCs) have important applications in communication, radar, and information security. In modern communication and radar systems, certain spectrum is reserved or ...prohibited from transmission, which leads to the so-called spectrally null constrained (SNC) problem. Compared with vast works on conventional CCCs, relatively little is known about SNC-CCCs. One objective of this paper is to derive several constructions of CCCs with more flexible settings from the graph of extended Boolean functions. This generalizes earlier achievements on CCCs from recent literature. Another objective of this paper is to employ the graphs of extended Boolean functions and polynomial representation of sequences to construct SNC-CCCs.
PDF
