Published in Science in China Series F: Information Sciences
Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks, Boolean functions used in many stream ciphers should possess high algebraic immunity. This paper presents two main results to find balanced Boolean functions with maximum algebraic immunity. Through swapping the values of tw...
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
Published in Moscow University Computational Mathematics and Cybernetics
Realization of Boolean functions in the class of oriented contact circuits (OCCs) with certain restrictions on the weight, number, and types of adjacent contacts is studied. Oriented contact circuits are considered in which, from an arbitrary vertex, at most λ arcs issue and at most ν different Boolean variables are used in the marks of the issuing...
Published in Annals of Operations Research
We consider the problem of dualizing a Boolean function f represented by a DNF. In its most general form, this problem is commonly believed not to be solvable by a quasi-polynomial total time algorithm. We show that if the input DNF is quadratic or is a special degree-k DNF, then dualization turns out to be equivalent to hypergraph dualization in h...
Published in Journal of Global Optimization
Substitution boxes, aka S-boxes, are a key component of modern crypto-systems. Several studies and developments were carried out on the problem of building high-quality S-boxes in the last few years. Qualities of such boxes, such as nonlinearity and balance, steer the robustness of modern block ciphers. This work is concerned with the construction ...
Published in Science China Information Sciences
Boolean functions used in stream ciphers against algebraic attacks are required to have a necessary cryptographic property-high algebraic immunity (AI). In this paper, Boolean functions of even variables with the maximum AI are investigated. The number of independent annihilators at the lowest degree of Boolean functions of even variables with the ...
Published in Mathematical Notes
A Boolean function f: {−1, +1}n → {−1, +1} is called the sign function of an integer-valued polynomial p(x) if f(x) = sgn(p(x)) for all x ∈ {−1, +1}n. In this case, the polynomial p(x) is called a perceptron for the Boolean function f. The weight of a perceptron is the sum of absolute values of the coefficients of p. We prove that, for a given func...
Published in Computational Mathematics and Mathematical Physics
Properties of the Boolean functions specified by the Zhegalkin polynomials in n variables of degree not greater than k are investigated from the viewpoint of placing their unit (zero) points on a unit cube. Properties of test sets for the Zhegalkin polynomials are considered, where the key role is played by the irredundant test sets. A deterministi...
Published in Journal of Control Theory and Applications
The structure of a canalizing function is discussed. Using a new matrix product, namely semitensor product, the logical function is expressed in its matrix form. From its matrix expression, a criterion is obtained to test whether a logical function is a canalizing function. Then a formula is obtained to calculate the number of canalizing functions....
