Narrow Results

The nonlinearity profile of Boolean functions is a generalization of the most important cryptographic criterion, called the (first order) nonlinearity. It is defined as the sequence of the minimum Hamming distances nl_r(f) between a given Boolean function f and all Boolean functions in the same number of variables and of degrees at most r, for r ≥ 1. This parameter, which has a close relationship with the Gowers norm, quantifies the resistance to cryptanalyses by low degree approximations of stream ciphers using the Boolean function f as combiner or as filter. The nonlinearity profile can also be defined for vectorial functions: it is the sequence of the minimum Hamming distances between the component functions of the vectorial function and all Boolean functions of degrees at most r, for r ≥ 1. The nonlinearity profile of the multiplicative inverse functions has been lower bounded in a previous paper by the same author. No other example of an infinite class of functions with unbounded nonlinearity profile has been exhibited since then. In this paper, we lower bound the whole nonlinearity profile of the (simplest) Dillon bent function (x,y) ↦ xy^2n/2-2, x, y ∈ 𝔽_2^n/2 and we exhibit another class of functions, for which bounding the whole profile of each of them comes down to bounding the first order nonlinearities of all functions.

In this paper we generalize two remarkable results on cryptographic properties of Boolean functions given by Tu and Deng [8] to the vectorial case. Firstly we construct vectorial bent Boolean functions with good algebraic immunity for all cases 1 ⩽ m ⩽ n, and with maximum algebraic immunity for some cases (n,m). Then by modifying F, we get vectorial balanced functions with optimum algebraic degree, good nonlinearity and good algebraic immunity for all cases , and with maximum algebraic immunity for some cases (n,m). Moreover, while Tu-Deng's results are valid under a combinatorial hypothesis, our results (Theorems 4 and 5) are true without this hypothesis.

In this paper, we study the nonexistence of bent functions in the class of Boolean functions without monomials of degree less than d in their algebraic normal forms (ANF). We prove that n-variable Boolean functions in such class are not bent when there are not more than n + d - 3 monomials in their ANFs. We also show that an n-variable Boolean function is not bent if it has no monomial of degree less than ⌈3n/8 + 3/4⌉ in its ANF.

Transient algebra is a multi-valued algebra for hazard detection in gate circuits. Sequences of alternating 0's and 1's, called transients, represent signal values, and gates are modeled by extensions of boolean functions to transients. Formulas for computing the output transient of a gate from the input transients are known for NOT, AND, OR and XOR gates and their complements, but, in general, even the problem of deciding whether the length of the output transient exceeds a given bound is NP-complete. We propose a method of evaluating extensions of general boolean functions. We study a class of functions for which, instead of evaluating the extensions on a given set of transients, it is possible to get the same values by using transients derived from the given ones, but having length at most 3. We prove that all functions of three variables, as well as certain other functions, have this property, and can be efficiently evaluated.

Based on Carlet-Feng functions, we present a method to construct odd variable Boolean functions with optimal algebraic immunity in this paper. The proposed functions can have the highest algebraic degree and a lower bound on the nonlinearity is also established.

In this paper, we give constructions of several classes of Boolean functions with four-valued Walsh spectra, which are derived from the indirect sum construction. The Walsh spectra and spectrum distributions of these functions are determined. The result of functions with four-valued Walsh spectra derived from Bent functions is used to research Bent functions and o-polynomials. By investigating the indirect sum, we also give constructions of plateaued functions and functions with five-valued Walsh spectra.

Boolean functions are fundamental bricks in the development of various applications in Cryptography and Coding theory by making benefit from the weights of related Boolean functions (Walsh spectrum). Towards this, the discrete Fourier transform (Walsh–Hadamard) plays a pivotal tool. The work in this paper is dedicated towards the algebraic and numerical degrees, together with the relationship between weights of Boolean function and their Walsh transforms. We introduce Walsh matrices and generalize them to any arbitrary Boolean function. This improves the complexity in computation of Walsh–Hadamard and Fourier transform in certain cases. We also discuss some useful results related to the degree of the algebraic normal form using Walsh–Hadamard transform.

In this paper, the notion of boolean linear differential operator (BLDO) on elementary cellular automata (ECA) is introduced and some of their more important properties are studied. Special attention is paid to those differential operators whose coefficients are the ECA with rule numbers 90 and 150.

To simplify the process for identifying 12 types of symmetric variables in the canonical Reed–Muller (CRM) algebra system, we propose a new symmetry detection algorithm based on AND-XOR expansion. By analyzing the relationships between the coefficient matrices of sub-functions and the order coefficient subset matrices based on AND-XOR expansion around two arbitrary logical variables, the constraint conditions of the order coefficient subset matrices are revealed for 12 types of symmetric variables. Based on the proposed constraints, the algorithm is realized by judging the order characteristic square value matrices. The proposed method avoids the complicated process for separating the AND–XOR expansion coefficients into different groups in the Reed–Muller transform methods and solves the problem of completeness in the RM type decomposition map method. The application results show that, compared with traditional methods the new algorithm is an optimal detection method in terms of applicability of the number of logical variables, detection types, and complexity of the identification process. The algorithm has been implemented in C language and tested on MCNC91 benchmarks. Experimental results show that the proposed algorithm is convenient and efficient.

In this paper, a general problem of the robust template decomposition with restricted weights for cellular neural networks (CNNs) implementing an arbitrary Boolean function is investigated. First, the geometric margin of a linear classifier with respect to a training data set is used to define the robustness of an uncoupled CNN implementing a linearly separable Boolean function. Second, maximal margin classifiers, i.e. robust CNNs, for such Boolean functions can be designed via support vector machines (SVMs). Third, some general properties of robust CNNs with or without restricted weights are discussed. Moreover, all robust CNNs with restricted weights are characterized. Finally, for an arbitrarily given Boolean function, we propose an algorithm, which is the generalized version of the well-known CFC algorithm, to find a sequence of robust uncoupled CNNs implementing the given Boolean function. Several illustrative examples demonstrate the efficiency of the proposed method. It will be seen that, in general, the tradeoff between the complexity regarding the number of terms in the decomposition and the guaranteed robustness regarding the geometric margins of the resulting CNNs must be made in the robust template decomposition with restricted weights.

In this paper, attribute reduction in variable precision rough set model is discussed. Several kinds of reducts preserving some of lower approximations, upper approximations, boundary regions and the unpredictable region are discussed. Relations among those kinds of reducts are investigated. As a basis for reduct computation, Boolean function representations of the preservation of lower approximations, upper approximations, boundary regions and the unpredictable region are discussed. Throughout this paper, the great difference between the analysis using variable precision rough sets and the classical rough set analysis is emphasized.

A substitution box is regarded as an eminent source of nonlinearity and perplexity in most of the block ciphers. In this work, we propose that the involvement of a local ring has a favorable influence on the highly desirable features of this nonlinear cryptographic system. We deploy the unit group of a local ring by considering its correspondence with the Galois field and design an algorithm that utilizes the algebraic properties of the local ring ${\mathbb{Z}}_{512}$, to synthesize a highly efficient S-box.

A Boolean quasilattice is an algebra with hyperidentities of the variety of Boolean algebras. In this paper, we give a functional representation of the free n-generated Boolean quasilattice with two binary, one unary and two nullary operations. Namely, we define the concept of super-Boolean function and prove that the free Boolean quasilattice with two binary, one unary and two nullary operations on n free generators is isomorphic to the Boolean quasilattice of super-Boolean functions of n variables.

In this paper, the set of some points, derived at which the degree of a Boolean function can be reduced by at least i, is defined as . We show the set of i-DPs (i-differential point) is closed to the operation XOR, and the origin i-DP still exists after taking a derivative on the Boolean function at a non-2-DP. In addition, ann-variable non-linear Boolean function of degree d has at most 2^n-d– 1 2-DPs. We prove that an n-bit cipher whose n component functions have common terms of degree n – 1, is not IND-CPA secure. We also show that an n-bit cipher with low degree d can be distinguished with obvious advantage and data complexity 2^d+1.