This paper discusses boolean functions satisfying the propagation criterion(PC) and their balancedness. Firstly, we discuss boolean functions with n variables that satisfy the PC with respect to all but three elements...
详细信息
This paper discusses boolean functions satisfying the propagation criterion(PC) and their balancedness. Firstly, we discuss boolean functions with n variables that satisfy the PC with respect to all but three elements in {0,1}n - {(0,...,0)}. For even n greater-than-or-equal-to 4, a necessary and sufficient condition is presented for boolean functions with n variables to satisfy the PC with respect to all but three elements in {0,1}n - {(0,...,0)]. From this condition, it is proved that all of these boolean functions are constructed from all perfectly nonlinear boolean functions with n-2 variables. For odd n greater-than-or-equal-to 3, it is shown that boolean functions with n variables satisfying the PC with respect to all but three elements in {0,1}n - {(0,...,0)} satisfy the PC with respect to all but one elements in it. Secondly, boolean functions satisfying the PC of degree n - 2 and their balancedness are considered. For even n greater-than-or-equal-to 4, it is proved that an upper bound on the degree of the PC is n - 3 for balance boolean functions with n variables. This bound is optimal for n = 4,6. It is also proved that, for odd n greater-than-or-equal-to 3, balanced boolean functions with n variables satisfying the PC of degree n - 2 satisfy the PC with respect to all but one elements in {0, 1}n - {(0,...,0)}.
In symmetric cryptology the resistance to attacks depends critically on the nonlinearity properties of the boolean functions describing cipher components like Substitution boxes (S-boxes). Some of the most effective m...
详细信息
In symmetric cryptology the resistance to attacks depends critically on the nonlinearity properties of the boolean functions describing cipher components like Substitution boxes (S-boxes). Some of the most effective methods known to generate functions that satisfy multiple criteria are based on evolutionary heuristics. In this paper, we improve on these algorithms by employing an adaptive strategy. Additionally, using recent improvements in the understanding of these combinatorial structures, we discover essential properties of the graph formed by affine equivalence classes of boolean functions, which offers several advantages as a conceptual model for multiobjective seeking evolutionary heuristics. Finally, we propose the first major global cooperative effort to discover new bounds for cryptographic properties of boolean functions.
Many static analyses for declarative programming/database languages use boolean functions to express dependencies among variables or argument positions. Examples include groundness analysis, arguably the most importan...
详细信息
Many static analyses for declarative programming/database languages use boolean functions to express dependencies among variables or argument positions. Examples include groundness analysis, arguably the most important analysis for logic programs, finiteness analysis and functional dependency analysis for databases. We identify two classes of boolean functions that have been used: positive and definite functions, and we systematically investigate these classes and their efficient implementation for dependency analyses. On the theoretical side, we provide syntactic characterizations and study the expressiveness and algebraic properties of the classes. In particular, we show that both are closed under existential quantification. On the practical side, we investigate various representations for the classes based on reduced ordered binary decision diagrams (ROBDDs), disjunctive normal form, conjunctive normal form, Blake canonical form, dual Blake canonical form, and a form specific to definite functions. We compare the resulting implementations of groundness analyzers based on the representations for precision and efficiency. (C) 1998 Elsevier Science B.V. All rights reserved.
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...
详细信息
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.
Recently, two classes of boolean functions with optimal algebraic immunity have been proposed by Carlet et al. and Wang et al., respectively. Although it appears that their methods are very different, it is proved in ...
详细信息
Recently, two classes of boolean functions with optimal algebraic immunity have been proposed by Carlet et al. and Wang et al., respectively. Although it appears that their methods are very different, it is proved in this paper that the two classes of boolean functions are in fact affine equivalent. Moreover, the number of affine equivalence classes of these functions is also studied.
boolean functions have a fundamental role in neural networks and machine learning. Enumerating these functions and significant subclasses is a highly complex problem. Therefore, it is of interest to study subclasses t...
详细信息
boolean functions have a fundamental role in neural networks and machine learning. Enumerating these functions and significant subclasses is a highly complex problem. Therefore, it is of interest to study subclasses that escape this limitation and can be enumerated by means of sequences depending on the number of variables. In this article, we obtain seven new formulas corresponding to enumerations of some subclasses of boolean functions. The versatility of these functions does the problem interesting to several different fields as game theory, hypergraphs, reliability, cryptography or logic gates.
A new framework concerning the construction of small-order resilient boolean functions whose nonlinearity is strictly greater than 2(n-1) -2(left perpendicularn/2right perpendicular) is given. First, a generalized Mai...
详细信息
A new framework concerning the construction of small-order resilient boolean functions whose nonlinearity is strictly greater than 2(n-1) -2(left perpendicularn/2right perpendicular) is given. First, a generalized Maiorana-McFarland construction technique is described, which extends the current approaches by combining the usage of affine and nonlinear functions in a controllable manner. It is shown that for any given m, this technique can be used to construct a large class of n-variable (n both even and odd) m-resilient degree-optimized boolean functions with currently best known nonlinearity. This class may also provide functions with excellent algebraic properties, measured through the resistance to (fast) algebraic attacks, if the number of n/2-variable affine subfunctions used in the construction is relatively low. Due to a potentially low hardware implementation cost, along with overall good cryptographic properties, this class of functions is an attractive candidate for the use in certain stream cipher schemes.
Homogeneous rotation symmetric boolean functions have been extensively studied in recent years because of their applications in cryptography. Little is known about the basic question of when two such functions in n va...
详细信息
Homogeneous rotation symmetric boolean functions have been extensively studied in recent years because of their applications in cryptography. Little is known about the basic question of when two such functions in n variables are affine equivalent. The simplest case of quadratic rotation symmetric functions which are generated by cyclic permutations of the variables in a single monomial was only settled in 2009, and the first substantial progress on the much more complicated cubic case came in 2010. In this paper, we show that much of the work on the cubic case can be extended to the quartic case. We also prove an exact formula for the number and sizes of the affine equivalence classes when n is a prime. (C) 2013 Elsevier Inc. All rights reserved.
In this paper, we concentrate on the design of 1-resilient boolean functions with desirable cryptographic properties. Firstly, we put forward a novel secondary construction to obtain 1-resilient functions. Next, we pr...
详细信息
In this paper, we concentrate on the design of 1-resilient boolean functions with desirable cryptographic properties. Firstly, we put forward a novel secondary construction to obtain 1-resilient functions. Next, we present the relationships between the properties of these constructed 1-resilient functions and that of the initial functions. Based on the construction and a class of bent functions on n variables, we can obtain a class of (n+3)-variable 1-resilient non-separable cryptographic functions with a high algebraic immunity, whose nonlinearity is equal to the bent concatenation bound 2(n+2)-2((n+2)/2). Furthermore, we propose a set of 1-resilient non-separable functions on odd number of variables with an optimal algebraic degree, a high algebraic immunity, and a high nonlinearity. Copyright (c) 2011 John Wiley & Sons, Ltd.
This paper proposes a new type of expression for boolean functions called lexicographical expressions. The basic idea is to impose an input ordering for factoring logical expressions. Several algebraic properties are ...
详细信息
This paper proposes a new type of expression for boolean functions called lexicographical expressions. The basic idea is to impose an input ordering for factoring logical expressions. Several algebraic properties are presented and relations with classical algebraic theory are established. The main result is that all elementary factorizations defined by (Cokernel, Kernel) pairs ''compatible'' with an input order are all ''algebraically compatible,'' i.e., are all parts of a single factorization of the function. Thus for a given input order a unique factorization is defined. This leads to fast division procedures. Basic techniques for obtaining lexicographical factorizations are presented. First, a precedence matrix and an updating procedure are defined and used later to select an input order and a corresponding compatible factorization. Second, a factorization technique respecting a fixed order is detailed. This method is then applied to multi-level synthesis using standard cells which was the original motivation of this work. The goal is to reduce wiring complexity. A lexicographical factorization leads to a wiring area reduction due to the structuring of the logic into layers in which the inputs enter the layout in the order given by the factorization. Experimental results comparing this approach to classical ones are given. These results include routing ratio measurements, routing structure observation, global area measurement and critical path estimation. All these results are analyzed after place and route, using an industrial tool (COMPASS Design Automation tool).
暂无评论