Boolean Function Construction And Research On Algebraic Attacks

Recently, algebraic attacks have received a lot of attention in the cryptographic com-munity. To resist many kinds of attacks, the Boolean functions used in stream ciphers should have good cryptographic properties:balancedness, high algebraic immunity, high algebraic degree, high nonlinearity and good immunity to fast algebraic attacks. The present Ph.D. dissertation is concerned with the constructions of Boolean functions with good cryptographic properties and algebraic attacks. Our contributions are as follows:First, we put forward a new method to construct cryptographically significant Boolean functions by using primitive polynomials, and construct three infinite classes of Boolean functions with good cryptographic properties:balancedness, optimum algebraic degree, optimum algebraic immunity, and a high nonlinearity.Second, we investigate equivalence of Boolean functions more deeply using a new method and discuss the number of Boolean functions in each equivalence class. We inves-tigate further the cryptographic properties including algebraic immunity, algebraic degree and nonlinearity of equivalence classes, and deduce tight bounds on them. We find that there are many equivalence classes of Boolean functions with optimum algebraic immunity, optimum algebraic degree and a good nonlinearity. Moreover, we discuss how to construct equivalence classes with desired properties and show that it is possible to construct prac-tical Boolean functions such that their equivalence classes have guaranteed cryptographic properties.Third, we investigate the resistance of Boolean functions against fast algebraic attacks and deduce a bound between fast algebraic immunity and higher order nonlinearity (it is the first time that a bound between these two cryptographic criteria is given). We then show that the fast algebraic immunity of the following two classes of Boolean functions is not good:(a) The repaired functions of the Tu-Deng function proposed by Carlet. The Tu-Deng function has optimum algebraic degree, optimum algebraic immunity and a very good nonlinearity. However, it is weak against fast algebraic attacks. Carlet found this weakness and also tried to repair it.(b) An infinite class of balanced functions proposed by Tang et al, having optimum algebraic degree, optimum algebraic immunity and a very high nonlinearity.Fourth, we introduce a new version of the algebraic attack, with applications towards cryptanalysis of stream ciphers. The new attack works in most cases and the complexity of it is much less than the classical algebraic attack. In particular, we give some observations on Trivium and EO, and find that the classical algebraic attacks on them can be sped up significantly.Last, we introduce a new type of algebraic attacks, called higher order algebraic at-tacks, with applications towards cryptanalysis of stream ciphers. Its efficiency is described through the new concept r-order algebraic immunity of a Boolean function. We show that the 2-order algebraic immunity of the following two classes of Boolean functions is equal to 1, which gives very efficient attacks on them (substantially and greatly outmatching previously known attacks):(a) The class of Carlet-Feng functions, proposed at Asiacrypt 2008, having optimum algebraic degree, optimum algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity.(b) The class of rotation symmetric Boolean functions, an interesting and well studied class of Boolean functions, which can be implemented efficiently.