Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity

Recent research shows that the class of rotation symmetric Boolean functions is potentially rich in functions of cryptographic significance. In this paper, based on the knowledge of compositions of an integer, we present two new kinds of construction of rotation symmetric Boolean functions having optimal algebraic immunity on either odd variables or even variables. Our new functions are of much better nonlinearity than all the existing theoretical constructions of rotation symmetric Boolean functions with optimal algebraic immunity. Further, the algebraic degree of our rotation symmetric Boolean functions are also high enough.     

Construction of balanced Boolean functions with high nonlinearity and good autocorrelation properties

Boolean functions with high nonlinearity and good autocorrelation properties play an important role in the design of block ciphers and stream ciphers. In this paper, we give a method to construct balanced Boolean functions of n variables, where n ≥ 10 is an even integer, satisfying strict avalanche criterion (SAC), and with high algebraic degree. Compared with the known balanced Boolean functions with SAC property, the constructed functions possess the highest nonlinearity and the best global avalanche characteristics property.     

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 designated-weight Boolean functions with highest algebraic immunity

Algebraic immunity has been considered as one of cryptographically significant properties for Boolean functions. In this paper, we study ∑d-1 i=0 (ni)-weight Boolean functions with algebraic immunity achiev-ing the minimum of d and n - d + 1, which is highest for the functions. We present a simpler sufficient and necessary condition for these functions to achieve highest algebraic immunity. In addition, we prove that their algebraic degrees are not less than the maximum of d and n - d + 1, and for d = n1 +2 their nonlinearities equalthe minimum of ∑d-1 i=0 (ni) and ∑ d-1 i=0 (ni). Lastly, we identify two classes of such functions, one having algebraic degree of n or n-1.     

A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity

In this paper, a combinatorial conjecture about binary strings is proposed. Under the assumption that the proposed conjecture is correct, two classes of Boolean functions with optimal algebraic immunity can be obtained. The functions in first class are bent, and then it can be concluded that the algebraic immunity of bent functions can take all possible values except one. The functions in the second class are balanced, and they have optimal algebraic degree and the best nonlinearity up to now.     

Further properties of several classes of Boolean functions with optimum algebraic immunity

Based on a method proposed by the first author, several classes of balanced Boolean functions with optimum algebraic immunity are constructed, and they have nonlinearities significantly larger than the previously best known nonlinearity of functions with optimal algebraic immunity. By choosing suitable parameters, the constructed n-variable functions have nonlinearity for even for odd n, where Δ(n) is a function increasing rapidly with n. The algebraic degrees of some constructed functions are also discussed.      

On the maximal component algebraic immunity of vectorial Boolean functions

Under study is the component algebraic immunity of vectorial Boolean functions. We prove a theorem on the correspondence between the maximal component algebraic immunity of a function and its balancedness. Some relationship is obtained between the maximal component algebraic immunity and matrices of a special form. We construct several functions with maximal component algebraic immunity in case of few variables.     

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 (2~m + 1)-variable symmetric Boolean functions with submaximum algebraic immunity 2~(m-1)

All (2m +1)-variable symmetric Boolean functions with submaximal algebraic immunity 2m-1 are described and constructed. The total number of such Boolean functions is 32 ·22m-3 +3m-2 · 24 - 2 for m≥2.     

On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2

We improve parts of the results of [T. W. Cusick, P. Stanica, Fast evaluation, weights and nonlinearity of rotation-symmetric functions, Discrete Mathematics 258 (2002) 289-301; J. Pieprzyk, C. X. Qu, Fast hashing and rotation-symmetric functions, Journal of Universal Computer Science 5 (1) (1999) 20-31]. It is observed that the n-variable quadratic Boolean functions, for , which are homogeneous rotation symmetric, may not be affinely equivalent for fixed n and different choices of s. We show that their weights and nonlinearity are exactly characterized by the cyclic subgroup 〈s−1〉 of Z_n. If , the order of s−1, is even, the weight and nonlinearity are the same and given by . If the order is odd, it is balanced and nonlinearity is given by .     

Sobolev multipliers,maximal functions and parabolic equations with a quadratic nonlinearity

We develop a general framework to describe global mild solutions to a Cauchy problem with small initial values concerning a general class of semilinear parabolic equations with a quadratic nonlinearity. This class includes the Navier–Stokes equations, the subcritical dissipative quasi-geostrophic equation and the parabolic–elliptic Keller–Segel system.     

On expansion of algebraic functions in power and Puiseux series, I

We present algorithms that (a) reduce an algebraic equation, defining an algebraic function, to a Fuchsian differential equation that this function satisfies; and (b) compute coefficients in the expansions of solutions of linear differential equations in the neighborhood of regular singularities via explicit linear recurrences. This allows us to compute the Nth coefficient (or N coefficients) of an algebraic function of degree d in O(dN) operations with O(d) storage (or O(dN) storage).     

Hölder behavior of optimal solutions and directional differentiability of marginal functions in nonlinear programming

This paper is concerned with the Hölder properties of optimal solutions of a nonlinear programming problem with perturbations in some fixed direction. The Hölder property is used to obtain the directional derivative for the marginal function.The authors are grateful for the referees' helpful comments, which led in particular to improvements in an early version of the paper.     

Algorithmic aspects of the substitution decomposition in optimization over relations,set systems and Boolean functions

In the last years, decomposition techniques have seen an increasing application to the solution of problems from operations research and combinatorial optimization, in particular in network theory and graph theory. This paper gives a broad treatment of a particular aspect of this approach, viz. the design of algorithms to compute the decomposition possibilities for a large class of discrete structures. The decomposition considered is thesubstitution decomposition (also known as modular decomposition, disjunctive decomposition, X-join or ordinal sum). Under rather general assumptions on the type of structure considered, these (possibly exponentially many) decomposition possibilities can be appropriately represented in acomposition tree of polynomial size. The task of determining this tree is shown to be polynomially equivalent to the seemingly weaker task of determining the closed hull of a given set w.r.t. a closure operation associated with the substitution decomposition. Based on this reduction, we show that for arbitrary relations the composition tree can be constructed in polynomial time. For clutters and monotonic Boolean functions, this task of constructing the closed hull is shown to be Turing-reducible to the problem of determining the circuits of the independence system associated with the clutter or the prime implicants of the Boolean function. This leads to polynomial algorithms for special clutters or monotonic Boolean functions. However, these results seem not to be extendable to the general case, as we derive exponential lower bounds for oracle decomposition algorithms for arbitrary set systems and Boolean functions.     

Asymptotic behavior and blow-up of solutions for infinitely degenerate semilinear parabolic equations with logarithmic nonlinearity

In this paper, we study the initial-boundary value problem for infinitely degenerate semilinear parabolic equations with logarithmic nonlinearity $u_t?{△}_{X}u=u\log ?|u|$, where $X=(X_1,X_2,?,X_m)$ is an infinitely degenerate system of vector fields, and ${△}_X:={\sum }_{j=1}^m{X}_j^2$ is an infinitely degenerate elliptic operator. Using potential well method, we first prove the invariance of some sets and vacuum isolating of solutions. Then, by the Galerkin method and the logarithmic Sobolev inequality, we obtain the global existence and blow-up at +∞ of solutions with low initial energy or critical initial energy, and we also discuss the asymptotic behavior of the solutions.     

Order and type of basic sets of polynomials associated with functions of algebraic semi block matrices

§ 1 is an introduction to basic sets of polynomials and to algebraic infinite matrices. In § 2 we investigate the order of basic sets associated with functions of algebraic semi block matrices whose elements are of a certain order of magnitude. In § 3 we investigate the type of such basic sets.