On the security of the Feng–Liao–Yang Boolean functions with optimal algebraic immunity against fast algebraic attacks

In the past few years, algebraic attacks against stream ciphers with linear feedback function have been significantly improved. As a response to the new attacks, the notion of algebraic immunity of a Boolean function f was introduced, defined as the minimum degree of the annihilators of f and f + 1. An annihilator of f is a nonzero Boolean function g, such that fg = 0. There is an increasing interest in construction of Boolean functions that possess optimal algebraic immunity, combined with other characteristics, like balancedness, high nonlinearity, and high algebraic degree. In this paper, we investigate a recently proposed infinite class of balanced Boolean functions with optimal algebraic immunity, optimum algebraic degree and much better nonlinearity than all the previously introduced classes of Boolean functions with maximal algebraic immunity. More precisely, we study the resistance of the functions against one of the new algebraic attacks, namely the fast algebraic attacks (FAAs). Using the special characteristics of the family members, we introduce an efficient method for the evaluation of their behavior against these attacks. The new algorithm is based on the well studied Berlekamp–Massey algorithm.     

Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity

So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with O(n²) time and O(n) space complexity. We use the term “Annihilator Immunity” instead of “Algebraic Immunity” referred in the recent papers [3–5, 9, 18, 19]. Please see Remark 1 for the details of this notational change     

On a method of derivation of lower bounds for the nonlinearity of Boolean functions

The calculation of the exact value of the rth order nonlinearity of a Boolean function (the power of the distance between the function and the set of functions is at most r) or the derivation of a lower bound for it is a complicated problem (especially for r > 1). Lower bounds for nonlinearities of different orders in terms of the value of algebraic immunity were obtained in a number of papers. These estimates turn out to be sufficiently strong if the value of algebraic immunity is maximum or close to maximum. In the present paper, we prove a statement that allows us to obtain fairly strong lower bounds for nonlinearities of different orders and for many functions with low algebraic immunity.     

On random orderings of variables for parity ordered binary decision diagrams

Ordered binary decision diagrams (OBDDs) are a model for representing Boolean functions. There is also a more powerful variant called parity OBDDs. The size of the representation of a given function depends in both these models on the chosen ordering of the variables. It is known that there are functions such that almost all orderings of their variables yield an OBDD of polynomial size, but there are also some exceptional orderings, for which the size is exponential. We prove that for parity OBDDs, the size for a random ordering and the size for the worst ordering are polynomially related. More exactly, for every ϵ>0 there is a number c>0 such that the following holds. If a Boolean function f of n variables is such that a random ordering of the variables yields a parity OBDD for f of size at most s with probability at least ϵ, where s≥n, then every ordering of the variables yields a parity OBDD for f of size at most s^c. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 233–239, 2000     

具有最优代数免疫度的2~m个变量的对称Boolean函数

本文给出了2m个变量的对称Boolean函数f具有最优代数免疫度AI2m(f)=2m-1的一个充分必要条件.由此得到一个递归公式,从而构造出全部具有最优代数免疫度的2m个变量的对称Boolean函数(m2).最后证明了这样的Boolean函数的个数为3·2m.     

Quantitative relation between noise sensitivity and influences

A Boolean function f: {0,1} ⁿ → {0,1} is said to be noise sensitive if inserting a small random error in its argument makes the value of the function almost unpredictable. Benjamini, Kalai and Schramm [3] showed that if the sum of squares of inuences of f is close to zero then f must be noise sensitive. We show a quantitative version of this result which does not depend on n, and prove that it is tight for certain parameters. Our results hold also for a general product measure µ _p on the discrete cube, as long as log1/p?logn. We note that in [3], a quantitative relation between the sum of squares of the inuences and the noise sensitivity was also shown, but only when the sum of squares is bounded by n ^?c for a constant c. Our results require a generalization of a lemma of Talagrand on the Fourier coefficients of monotone Boolean functions. In order to achieve it, we present a considerably shorter proof of Talagrand’s lemma, which easily generalizes in various directions, including non-monotone functions.     

On second-order nonlinearity and maximum algebraic immunity of some bent functions in \mathcal{PS}^{+}

The rth-order nonlinearity and algebraic immunity of Boolean function play a central role against several known attacks on stream and block ciphers. Since its maximum equals the covering radius of the rth-order Reed-Muller code, it also plays an important role in coding theory. The computation of exact value or high lower bound on the rth-order nonlinearity of a Boolean function is very complected/challenging problem, especially when r>1. In this article, we identify a subclass of \({\mathcal{D}}_{0}\) type bent functions constructed by modifying well known Dillon functions having sharper bound on their second-order nonlinearity. We further, identify a subclass of bent functions in \({\mathcal {PS}}^{+}\) class with maximum possible algebraic immunity. The result is proved by using the well known conjecture proposed by Tu and Deng (Des. Codes Cryptogr. 60(1):1–14, 2011). To obtain rth-order nonlinearity (r>2), that is, whole nonlinearity profile of the constructed bent functions is still an open problem.     

On closures verifying that the interior of a closed element is closed

We give significant improvements to the Graham, Knuth & Motzkin result: if R is any binary relation, R ^+c+c+ = R ^+c+c (where P ⁺ denotes the transitive closure of the binary relation P, and P ^c its Boolean complement)     

Equivalence classes of functions between finite groups

Two types of equivalence relation are used to classify functions between finite groups into classes which preserve combinatorial and algebraic properties important for a wide range of applications. However, it is very difficult to tell when functions equivalent under the coarser (“graph”) equivalence are inequivalent under the finer (“bundle”) equivalence. Here we relate graphs to transversals and splitting relative difference sets (RDSs) and introduce an intermediate relation, canonical equivalence, to aid in distinguishing the classes. We identify very precisely the conditions under which a graph equivalence determines a bundle equivalence, using transversals and extensions. We derive a new and easily computed algebraic measure of nonlinearity for a function f, calculated from the image of its coboundary ∂f. This measure is preserved by bundle equivalence but not by the coarser equivalences. It takes its minimum value if f is a homomorphism, and takes its maximum value if the graph of f contains a splitting RDS.     

A systematic method of constructing Boolean functions with optimal algebraic immunity based on the generator matrix of the Reed–Muller code

Because of the recent algebraic attacks, optimal algebraic immunity is now an absolutely necessary (but not sufficient) property for Boolean functions used in stream ciphers. In this paper, we firstly determine the concrete coefficients in the linear expression of the column vectors with respect to a given basis of the generator matrix of Reed–Muller code, which is an important tool for constructing Boolean functions with optimal algebraic immunity. Secondly, as applications of the determined coefficients, we provide simpler and direct proofs for two known constructions. Further, we construct new Boolean functions on odd variables with optimal algebraic immunity based on the generator matrix of Reed–Muller code. Most notably, the new constructed functions possess the highest nonlinearity among all the constructions based on the generator matrix of Reed–Muller code, although which is not as good as the nonlinearity of Carlet–Feng function. Besides, the ability of the new constructed functions to resist fast algebraic attacks is also checked for the variable \(n=11,13\) and 15.     

Improving the high order nonlinearity lower bound for Boolean functions with given algebraic immunity

Algebraic immunity is a recently introduced cryptographic parameter for Boolean functions used in stream ciphers. If pAI(f) and pAI(f⊕1) are the minimum degree of all annihilators of f and f⊕1 respectively, the algebraic immunity AI(f) is defined as the minimum of the two values. Several relations between the new parameter and old ones, like the degree, the r-th order nonlinearity and the weight of the Boolean function, have been proposed over the last few years.In this paper, we improve the existing lower bounds of the r-th order nonlinearity of a Boolean function f with given algebraic immunity. More precisely, we introduce the notion of complementary algebraic immunity defined as the maximum of pAI(f) and pAI(f⊕1). The value of can be computed as part of the calculation of AI(f), with no extra computational cost. We show that by taking advantage of all the available information from the computation of AI(f), that is both AI(f) and , the bound is tighter than all known lower bounds, where only the algebraic immunity AI(f) is used.     

On (2<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript> + 1)-variable symmetric Boolean functions with submaximum algebraic immunity 2<Superscript><Emphasis Type="Italic">m</Emphasis>−1</Superscript>

All (2 ^m + 1)-variable symmetric Boolean functions with submaximal algebraic immunity 2 ^m−1 are described and constructed. The total number of such Boolean functions is 3² · 2^2m−3 +3 ^m−2 · 2⁴ − 2 for m ⩾ 2. This work was supported by the Major State Basic Research Development Program of China (Grant No. 2004CB3180004) and National Natural Science Foundation of China (Grant No. 60433050)     

布尔函数的代数免疫性与设计准则

本文讨论了布尔函数的重量与代数免疫性之间的关系,给出了判断布尔函数是否有低次零化子的一个充分条件,并对由几类传统的构造方法所获得的布尔函数的代数免疫性进行了分析.     

The fraction of large random trees representing a given Boolean function in implicational logic

We consider the logical system of Boolean expressions built on the single connector of implication and on positive literals. Assuming all expressions of a given size to be equally likely, we prove that we can define a probability distribution on the set of Boolean functions expressible in this system. Then we show how to approximate the probability of a function f when the number of variables grows to infinity, and that this asymptotic probability has a simple expression in terms of the complexity of f. We also prove that most expressions computing any given function in this system are “simple”, in a sense that we make precise. The probability of all read‐once functions of a given complexity is also evaluated in this model. At last, using the same techniques, the relation between the probability of a function and its complexity is also obtained when random expressions are drawn according to a critical branching process. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Covering Sequences of Boolean Functions and Their Cryptographic Significance

We introduce the notion of covering sequence of a Boolean function, related to the derivatives of the function. We give complete characterizations of balancedness, correlation immunity and resiliency of Boolean functions by means of their covering sequences. By considering particular covering sequences, we define subclasses of (correlation-immune) resilient functions. We derive upper bounds on their algebraic degrees and on their nonlinearities. We give constructions of resilient functions belonging to these classes. We show that they achieve the best known trade-off between order of resiliency, nonlinearity and algebraic degree.     

Transcendence measures and algebraic growth of entire functions

In this paper we obtain estimates for certain transcendence measures of an entire function f. Using these estimates, we prove Bernstein, doubling and Markov inequalities for a polynomial P(z,w) in ℂ² along the graph of f. These inequalities provide, in turn, estimates for the number of zeros of the function P(z,f(z)) in the disk of radius r, in terms of the degree of P and of r. Our estimates hold for arbitrary entire functions f of finite order, and for a subsequence {n _j } of degrees of polynomials. But for special classes of functions, including the Riemann ζ-function, they hold for all degrees and are asymptotically best possible. From this theory we derive lower estimates for a certain algebraic measure of a set of values f(E), in terms of the size of the set E.     

代数免疫度为1的布尔函数

布尔函数的代数免疫度是在流密码的代数攻击中所产生的重要概念.研究了代数免疫度为1的布尔函数,得到的主要结果有:对代数免疫度为1的布尔函数给出了一个谱刻画,给出了其个数的精确计数公式,最后给出了此类函数的非线性度的紧的上界.     

Relations between threshold and <Emphasis Type="Italic">k</Emphasis>-interval Boolean functions

Every k-interval Boolean function f can be represented by at most k intervals of integers such that vector x is a truepoint of f if and only if the integer represented by x belongs to one of these k (disjoint) intervals. Since the correspondence of Boolean vectors and integers depends on the order of bits an interval representation is also specified with respect to an order of variables of the represented function. Interval representation can be useful as an efficient representation for special classes of Boolean functions which can be represented by a small number of intervals. In this paper we study inclusion relations between the classes of threshold and k-interval Boolean functions. We show that positive 2-interval functions constitute a (proper) subclass of positive threshold functions and that such inclusion does not hold for any k>2. We also prove that threshold functions do not constitute a subclass of k-interval functions, for any k.     

An improvement on the complexity of factoring read-once Boolean functions

Read-once functions have gained recent, renewed interest in the fields of theory and algorithms of Boolean functions, computational learning theory and logic design and verification. In an earlier paper [M.C. Golumbic, A. Mintz, U. Rotics, Factoring and recognition of read-once functions using cographs and normality, and the readability of functions associated with partial k-trees, Discrete Appl. Math. 154 (2006) 1465-1677], we presented the first polynomial-time algorithm for recognizing and factoring read-once functions, based on a classical characterization theorem of Gurvich which states that a positive Boolean function is read-once if and only if it is normal and its co-occurrence graph is P₄-free.In this note, we improve the complexity bound by showing that the method can be modified slightly, with two crucial observations, to obtain an O(n|f|) implementation, where |f| denotes the length of the DNF expression of a positive Boolean function f, and n is the number of variables in f. The previously stated bound was O(n²k), where k is the number of prime implicants of the function. In both cases, f is assumed to be given as a DNF formula consisting entirely of the prime implicants of the function.     

On power deformations of univalent functions

For an analytic function f (z) on the unit disk |z| < 1 with f (0) = f′(0) − 1 = 0 and f (z) ≠ 0, 0 < |z| < 1, we consider the power deformation f _c (z) = z(f (z)/z) ^c for a complex number c. We determine those values c for which the operator maps a specified class of univalent functions into the class of univalent functions. A little surprisingly, we will see that the set is described by the variability region of the quantity zf′(z)/ f (z), |z| < 1, for most of the classes that we consider in the present paper. As an unexpected by-product, we show boundedness of strongly spirallike functions.