Construction And Analysis Of Boolean Functions For Cryptography

Boolean functions play a central role in many cryptosystems. Design and construction of Boolean functions which satisfy cryptographic criteria are required. But there exists restriction between some criteria. It is therefore necessarry to study the relationship of these cryptographic criteria. The interrelationship among criteria of Boolean functions as well as the construction of optimized algebraic immunity functions is investigated in this dissertation. The main results are as follows.Firstly, the conjecture about the algebraic degrees of balanced elementary symmetric Boolean functions on odd numbers of variables, which was proposed by Cusick et al. in 2008[9], is discussed. All n-variable nonlinear balanced elementary symmetric Boolean functions are characterized, except for those whose degrees can be divided by 2^t+1 when n = 2^t+1l-1. The degrees of these nonlinear balanced elementary Boolean functions are proved to be of this form d = 2^k(1≤k≤t).Secondly, a construction of Boolean functions on even numbers of variables with optimum algebraic immunity is presented by modifying all outputs of majority function f ( x ) corresponding to the inputs belonging to two orbits. The number of constructed Boolean functions is greater than2^C_nn/2. Particularly, if f( x )is balanced, the constructed functions are also balanced. A general construction is also proposed according to the properties of circulant matrix. Moreover, a sufficient condition for singular circulant matrices is raised.Thirdly, the relationship between m-order FCI and m-order generalizedε-correlation immunity of Boolean function is discussed by using the probabilistic methods. When m = 1, we prove the equivalence of FCI and generalizedε-correlation immunity and when m > 1, an inequality between them is given. When the support set of a Boolean function is a flat, we obtain its FCI and generalizedε-correlation immunity. This shows that FCI is better than generalizedε-correlation immunity when characterizing correlation immunity of Boolean functions.