Find Better Boolean Functions in the Affine Equivalence Class

The Boolean functions in an affine equivalence class are of the same algebraicdegree and nonlinearity, but may satisfy different order of correlation immunity and propa-gation criterion. A method is presented in this paper to find Boolean functions with higherorder correlation immunity or satisfying higher order propagation criterion in an affine equiv-alence class. 8 AES s-box functions are not better Boolean functions in their affine equiva-lence class.

On the construction of cryptographically strong Boolean functions with desirable trade-off

This paper proposes a practical algorithm for systematically generating strong Boolean functions (f:GF(2) n →GF(2)) with cryptographic meaning. This algorithm takes bent function as input and directly outputs the resulted Boolean function in terms of truth table sequence. This algorithm was used to develop two classes of balanced Boolean functions, one of which has very good cryptographic properties:nl(f)=2 2k?1?2k+2k?2 (n=2k), with the sum-of-squares avalanche characteristic off satisfying σf=24k+23k+2+23k-2 and the absolute avalanche characteristic off satisfying σf=24k+23k+2+23k-2. This is the best result up to now compared to existing ones. Instead of bent sequences, starting from random Boolean functions was also tested in the algorithm. Experimental results showed that starting from bent sequences is highly superior to starting from random Boolean functions. Key words Boolean functions - Bent sequences - Nonlinearity - GAC - PC - Balancedness Document code A CLC number TP301.6

Evolutionary Design of Boolean Functions

We use evolutionaly computing to synthesize Boolean functions randomly Byusing specific crossover and mutation operator, in evolving process and modifying search space andfitness function, we get some high non-linearity functions which have other good cryptographycharacteristics such as autocorrelation etc Comparing to other heuristic search techniques,evolutionary computing approach is more effective because of global search strategy and implicitparallelism.

Construction of Odd-Variable Boolean Function with Maximum Algebraic Immunity Using Univariate Polynomial Representation

To protect against algebraic attacks, a high algebraic immunity is now an important criterion for Boolean functions used in stream ciphers. In this paper, a new method based on a univariate polynomial representation of Boolean functions is proposed. The proposed method is used to constmct Boolean functions with an odd number of variables and with maximum algebraic immunity. We also discuss the nonlinearity of the constructed functions. Moreover, a lower bound is deter- mined for the number of Boolean functions with rmximum algebraic immunity.

On Boolean Functions Associated to Finite Aligned Spaces

Boolean or switching functions can be associated to finite aligned spaces in a way similar to the way they can be associated to finite topological spaces. We prove a characterization of switching functions associated to aligned spaces which is similar to the one we have given for switching functions associated to finite topological spaces.

A Review of Lightweight Cryptographic Schemes and Fundamental Cryptographic Characteristics of Boolean Functions

In this paper, we survey a number of studies in the literature on improving lightweight systems in the Internet of Things (IoT). The paper illustrates recent development of Boolean cryptographic function Application and how it assists in using hardware such as the internet of things. For a long time there seems to be little progress in applying pure mathematics in providing security since the wide progress made by George Boole and Shannon. We discuss cryptanalysis of Boolean functions to avoid trapdoors and vulnerabilities in the development of block ciphers. It appears that there is significant progress. A comparative analysis of lightweight cryptographic schemes is reported in terms of execution time, code size and throughput. Depending on the schemes and the structure of the algorithms, these parameters change but remain within reasonable values making them suited for Internet of things applications. The driving force of lightweight cryptography (LWC) stems mainly from its direct applications in the real world since it provides solutions to actual problems faced by designers of IoT systems. Broadly speaking, lightweight cryptographic algorithms are designed to achieve two main goals. The first goal of a cryptographic algorithm is to withstand all known cryptanalytic attacks and thus to be secure in the black-box model. The second goal is to build the cryptographic primitive in such a way that its implementations satisfy a clearly specified set of constraints that depend on a case-by-case basis.

Global Avalanche Characteristics of Boolean Functions by Concatenation

In order to measure the correlation propeties of two Boolean functions,the global avalanche characteristics of Boolean functions constructed by concatenation are discussed,i.e.,f_1‖f_2and f_1‖f_2‖f_3‖f_4.Firstly,for the function f = f_1‖f_2,the cross-correlation function of f_1,f_2 in the special condition are studied.In this case,f,f_1,f_2 must be in desired form.By computing their sum-of-squares indicators,the crosscorrelation function between f_1,f_2 is obtained.Secondly,for the function g = f_1‖f_2‖f_3‖f_4,by analyzing the relation among their auto-correlation functions,their sum-of-squares indicators are investigated.Based on them,the sum-of-squares indicators of functions obtained by Canteaut et al.are investigated.The results show that the correlation property of g is good when the correlation properties of Boolean functions f_1,f_2,f_3,f_4 are good.

ENUMERATING CORRELATION-IMMUNE BOOLEAN FUNCTIONS OF ORDER ONE

A large class of linear structural functions(LSF) satisfying the condition of correlational immunity of order one are constructed by studying the linear structural Boolean functions. With these new founded functions, the known enumeration bounds of correlation-immune functions of order one are greatly improved. In fact, the best, up to now, lower bound is found.

The Nonlinear Filter Boolean Function of LILI-128 Stream Cipher Generator Is Successfully Broken Based on the Complexity of Nonlinear 0 1 Symbol Sequence

The nonlinear filter Boolean function of LILI-128 stream cipher generator is studied in this paper. First we measure the complexity of the stream ciphers sequence of LILI-128 stream cipher generator and obtain the shortest bit stream sequence reconstructed Boolean function of nonlinear filter in LILI-128 stream cipher generator. Then the least nonlinear Boolean function of generating stream cipher sequence is reconstructed by clusterig, nonlinear predictive and nonlinear synchronization from shortest bit stream sequence. We have verified the correctness of our reconstruction result by simulating the block diagram of Lili-128 keystream generator using our getting Boolean function and implement designers’ reference module of Lili-128 stream cipher public online, and two methods produce the same synchronous keystream sequence under same initial state, so that our research work proves that the nonlinear Boolean function of LILI-128 stream cipher generator is successfully broken.

Some results on the algebraic immunity of Boolean functions

From the motivation of algebraic attacks on stream and block ciphers,the concept of algebraic immunity（AI） of a Boolean function was introduced and studied extensively.High algebraic immunity is a necessary condition for resisting algebraic attacks.In this paper,we give some lower bounds on the algebraic immunity of Boolean functions.The results are applied to give lower bounds on the AI of symmetric Boolean functions and rotation symmetric Boolean functions.Some balanced rotation symmetric Boolean functions with their AI near the maximum possible value「n/2」are constructed.

On Decision Tree Complexity of Boolean Function andYao's Question

A Boolean function /(x1,x2,…,xn) is said to be elusive, if every decision tree algorithm computing / must examine all n variables in the worst case. In 1988, A.C.C. Yao introduced a question: Is any nontrivial monotone Boolean function that is invariant under the transitive act of group Cm × Cn elusive? The positive answer to this question supports the famous Rivest-Vuillemin conjecture on decision tree complexity. In this paper, we shall partly answer this question.

A Study on Monotone Self-Dual Boolean Functions

This paper shows that monotone self-dual Boolean functions in irredundant disjuntive normal form （IDNF） do not have more variables than disjuncts. Monotone self-dual Boolean functions in IDNF with the same number of variables and disjuncts are examined. An algorithm is proposed to test whether a monotone Boolean function in IDNF with n variables and n disjuncts is self-dual. The runtime of the algorithm is O（n3）.

Construction of 1-Resilient Boolean Functions with Optimal Algebraic Immunity and Good Nonlinearity

This paper presents a construction for a class of 1-resilient functions with optimal algebraic immunity on an even number of variables. The construction is based on the concatenation of two balanced functions in associative classes. For some n, a part of 1-resilient functions with maximum algebraic immunity constructed in the paper can achieve almost optimal nonlinearity. Apart from their high nonlinearity, the functions reach Siegenthaler＇s upper bound of algebraic degree. Also a class of l-resilient functions on any number n 〉 2 of variables with at least sub-optimal algebraic immunity is provided.

The autocorrelation distribution of balanced Boolean function

The global avalanche characteristics （the sum- of-squares indicator and the absolute indicator） measure the overall avalanche characteristics of a cryptographic Boolean function. Sung et al. （1999） gave the lower bound on the sum- of-squares indicator for a balanced Boolean function satisfy- ing the propagation criterion with respect to some vectors. In this paper, if balanced Boolean functions satisfy the propaga- tion criterion with respect to some vectors, we give three nec- essary and sufficient conditions on the auto-correlation distri- bution of these functions reaching the minimum the bound on the sum-of-squares indicator. And we also find all Boolean functions with 3-variable, 4-variable, and 5-variable reaching the minimum the bound on the sum-of-squares indicator.

On the 2~m-variable symmetric Boolean functions with maximum algebraic immunity

The properties of the 2m-variable symmetric Boolean functions with maximum al- gebraic immunity are studied in this paper. Their value vectors, algebraic normal forms, and algebraic degrees and weights are all obtained. At last, some necessary conditions for a symmetric Boolean function on even number variables to have maximum algebraic immunity are introduced.

A Class of Rotation Symmetric Boolean Functions with Optimum Algebraic Immunity

For an odd integer n ≥ 7, this paper presented a class of n-variable rotation symmetric Boolean functions （RSBFs） with optimum algebraic immunity. The nonlinearity of the constructed functions is determined.

Analysis of affinely equivalent Boolean functions

By some basic transforms and invariant theory, we give two results： 1） an algorithm, which can be used to judge if two Boolean functions are affinely equivalent and to obtain the equivalence relationship if they are equivalent. This is useful in studying Boolean functions and in engineering. For example, we classify all 8-variable homogeneous bent functions of degree 3 into two classes; 2） Reed-Muller codes R（4,6）/R（1,6）, R（3,7）/R（1,7） are classified efficiently.

Construction and enumeration of Boolean functions with maximum algebraic immunity

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 two bits, and then generalizing the result to swap some pairs of bits of the symmetric Boolean function constructed by Dalai, a new class of Boolean functions with maximum algebraic immunity are constructed. Enumeration of such functions is also n given. For a given function p（x） with deg（p（x）） 〈 [n/2], we give a method to construct functions in the form p（x）＋q（x） which achieve the maximum algebraic immunity, where every term with nonzero coefficient in the ANF of q（x） has degree no less than [n/2].

Boolean Functions with Four-Valued Walsh Spectra

Three classes of Boolean functions with four-valued Walsh spectra are presented and their Walsh spectrum distributions are determined. They are derived from Bent functions of the MaioranaMc Farland and Dillon PS ap types and of the monomial form Tr1^2m（λx^r（2^m-1）） by complementing the values of the Bent functions at two points.

RESULTS ON PERMUTATION SYMMETRIC BOOLEAN FUNCTIONS

This paper provides a systematic method on the enumeration of various permutation symmetric Boolean functions. The results play a crucial role on the search of permutation symmetric Boolean functions with good cryptographic properties. The proposed method is algebraic in nature. As a by-product, the authors correct and generalize the corresponding results of St^nic~ and Maitra （2008）. Further, the authors give a complete classification of block-symmetric bent functions based on the results of Zhao and Li （2006）, and the result is the only one classification of a certain class of permutation symmetric bent functions after the classification of symmetric bent functions proposed by Savicky （1994）.