A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials

A lower estimate of the Shannon function for the complexity of three-valued logic functions in the class of polarized polynomials is found.     

Synthesis of formulas whose complexity and depth do not exceed the asymptotically best estimates of high degree of accuracy

We study problems concerning optimal realizations of arbitrary Boolean functions by formulas in the standard basis {&;, V, ¬} in the presence of two optimality criteria: the depth and the complexity. Both the complexity and depth of Boolean functions are investigated from the point of view of so-called asymptotically best estimates of high degree of accuracy for the corresponding Shannon functions. Such estimates produce an asymptotics not only for the Shannon function, but also for the first remainder term of its standard asymptotic expansion. For any Boolean function depending on n variables, we prove that it is possible to construct a realizing formula in the basis {&;, V, ¬} so that its depth and complexity do not exceed values of the corresponding Shannon functions for the argument equal to n in the sense of asymptotic estimates of high degree of accuracy.     

Depth of <Emphasis Type="Italic">α</Emphasis>-completions of systems of Boolean functions

A problem of realization of Boolean functions by α-formulas is considered. These formulas are such that each subformula contains not more than one nontrivial principal subformula. The depth is considered as a complexity measure of a formula. Upper and lower polynomial estimates of Shannon functions for α-completions of finite systems of Boolean functions are obtained.     

Complexity of realization of Boolean functions from some classes related to finite grammars by formulas of alternation depth 3

The realization complexity of Boolean functions associated with finite grammars in the class of formulas of alternation depth 3 is studied. High accuracy asymptotic bounds are obtained for the corresponding Shannon function.     

On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

Representations of Boolean functions by exclusive-OR sums (modulo 2) of pseudoproducts is studied. An ExOR-sum of pseudoproducts (ESPP) is the sum modulo 2 of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this form, and the length of a Boolean function in the class of ESPPs is defined as the minimum length of an ESPP representing this function. The Shannon function L ^ESPP(n) of the length of Boolean functions in the class of ESPPs is considered, which equals the maximum length of a Boolean function of n variables in this class. Lower and upper bounds for the Shannon function L ^ESPP(n) are found. The upper bound is proved by using an algorithm which can be applied to construct representations by ExOR-sums of pseudoproducts for particular Boolean functions.     

Complexity of realization of functions from a class of three-valued logic by formulas of special type

A set of functions of the three-valued logic is considered and upper estimates for the Shannon function in the class of formulas of special form are obtained for this set. Some examples of sequences of functions from this set are considered and exponential lower estimates of complexity are obtained. In this case the values of the Shannon function are obtained for the considered class with the accuracy up to an additive constant.     

Lower estimates of circuit complexity in the basis of antichain functions

The antichain function is a characteristic function of an antichain in the Boolean cube. The set of antichain functions is an infinite complete basis. We study the computational complexity of Boolean functions over an antichain functional basis. In this paper we prove an asymptotic lower bound of order $\sqrt n $ for the computational complexity of a linear function, a majority function, and almost all Boolean functions of n variables.     

Complexity of Boolean functions in the class of polarized polynomial forms

It is proved that values of Shannon functions in the class of polarized polynomial forms (generalized Reed-Muller forms) coincide for classes of all Boolean functions and all symmetric Boolean functions; a formula computing estimates for these functions is derived. Translated fromAlgebra i Logika, Vol. 34, No. 3, pp. 323-326, May-June, 1995.     

Generic cryptographic weakness of k-normal Boolean functions in certain stream ciphers and cryptanalysis of grain-128

This paper considers security implications of k-normal Boolean functions when they are employed in certain stream ciphers. A generic algorithm is proposed for cryptanalysis of the considered class of stream ciphers based on a security weakness of k-normal Boolean functions. The proposed algorithm yields a framework for mounting cryptanalysis against particular stream ciphers within the considered class. Also, the proposed algorithm for cryptanalysis implies certain design guidelines for avoiding certain weak stream cipher constructions. A particular objective of this paper is security evaluation of stream cipher Grain-128 employing the developed generic algorithm. Contrary to the best known attacks against Grain-128 which provide complexity of a secret key recovery lower than exhaustive search only over a subset of secret keys which is just a fraction (up to 5%) of all possible secret keys, the cryptanalysis proposed in this paper provides significantly lower complexity than exhaustive search for any secret key. The proposed approach for cryptanalysis primarily depends on the order of normality of the employed Boolean function in Grain-128. Accordingly, in addition to the security evaluation insights of Grain-128, the results of this paper are also an evidence of the cryptographic significance of the normality criteria of Boolean functions.     

Complexity of the Realization of a Linear Boolean Function in the Class of <Emphasis Type="Italic">π</Emphasis>-Schemes

Using Khrapchenko’s method, we obtain the exact lower bound of 40 for the complexity in the class of π-schemes of a linear Boolean function depending substantially on 6 variables. We give a simplified proof of several lower bounds for the complexity of linear Boolean functions which are previously obtained on the basis of the same method.     

On estimates of Shannon functions of the length of unit tests for transpositions of variables

A nontrival upper estimate of the form n √2n (1 + o(1)) is proposed for the Shannon function of the length of the unit checking test for transpositions of variables of a Boolean function from P ₂ ⁿ , and it is proved that the Shannon function of the length of a unit diagnostic test for transpositions of variables of a Boolean function from P ₂ ⁿ has an asymptotics of the form n ²/2.     

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ^ESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that L ^ESPP(n) = ? (2 ⁿ /n ²). The quantity L ^ESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions.     

Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms

The problem of constructing simple disjunctive normal forms (DNFs) of Boolean functions with a small number of zeros is considered. The problem is of interest in the complexity analysis of Boolean functions and in its applications to data analysis. The method used is a further development of the reduction approach to the construction of DNFs of Boolean functions. A key idea of the reduction method is that a Boolean function is represented as a disjunction of Boolean functions with fewer zeros. In a number of practically important cases, this technique makes it possible to considerably reduce the complexity of DNF implementations of Boolean functions.     

Incomparable integrals and approximate calculation of monotone Boolean functions

The number of incomparable k-dimensional intervals in the Boolean n-cube is estimated. The result is used to estimate the complexity of approximate computation of an arbitrary monotone Boolean function of n variables.     

Recognizing the nonrepeating property in an arbitrary basis

Two classical problems are considered: recognizing the properties of a Boolean function given a column of its values and constructing a diagnostic test. The problems are investigated for nonrepeating functions in an arbitrary basis B. For the first problem, the decomposition method is applied to prove linear complexity of the corresponding sequential circuits; for the second problem we derive the order of the Shannon functions for a number of bases, in particular, for the basis of all functions of four variables. __________ Translated from Prikladnaya Matematika i Informatika, No. 23, pp. 67–84, 2006.     

Proof of lower estimates for the complexity of self-correcting circuits by the method of basis changing

A method for obtaining new lower estimates for the implementation complexity of individual Boolean functions is presented in the paper. The method is based on the transition from some considered basis to another one possessing already known good lower estimates for the complexity of those functions. The effective use of this method is illustrated by the example of obtaining the asymptotic value for the implementation complexity of threshold functions by self-correcting circuits composed of multiple-input elements.     

Tests for multiple monotone symmetric conglutinations of variables in Boolean functions

A linear lower and a quadratic upper bound on the Shannon function for the length of a detecting test for multiple monotone symmetric conglutinations are proved. Additionally, the exact value of the Shannon function for the length of a diagnostic test for multiple monotone symmetric conglutinations is found. Some of the variables of a Boolean function are said to conglutinate if each of them is replaced by a function of these variables. A conglutination is called multiple if there are several groups of conglutinated variables.     

Complexity of linear and majority functions in the basis of antichain functions

The complexity of realization of Boolean functions by circuits of functional elements in the basis consisting of all characteristic functions of antichains over a Boolean cube is studied. It is proved that the complexity of realization of an n-variable parity function is \(\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor \) and the complexity of its negation equals the complexity of the n-variable majority function which is \(\left\lceil {\frac{{n + 1}}{2}} \right\rceil \).     

The complexity of pseudo-linear functions

Upper and lower estimates for the complexity of functions of the 3-valued logic taking values from the set {0, 1} with linear Boolean restrictions are derived.     

Linearization of nonlinear filter generators and its application to cryptanalysis of stream ciphers

Nonlinear filter generators are commonly used as keystream generators in stream ciphers. A nonlinear filter generator utilizes a nonlinear filtering function to combine the outputs of a linear feedback shift register (LFSR) to improve the linear complexity of keystream sequences. However, the LFSR-based stream ciphers are still potentially vulnerable to algebraic attacks that recover the key from some keystream bits. Although the known algebraic attacks only require polynomial time complexity of computations, all have their own constraints. This paper uses the linearization of nonlinear filter generators to cryptanalyze LFSR-based stream ciphers. Such a method works for any nonlinear filter generators. Viewing a nonlinear filter generator as a Boolean network that evolves as an automaton through Boolean functions, we first give its linearization representation. Compared to the linearization representation in Limniotis et al. (2008), this representation requires lower spatial complexity of computations in most cases. Based on the representation, the key recoverability is analyzed via the observability of Boolean networks. An algorithm for key recovery is given as well. Compared to the exhaustive search to recover the key, using this linearization representation requires lower time complexity of computations, though it leads to exponential time complexity.