Construction And Analysis Of Boolean Functions For Stream Ciphers

Boolean functions are the building blocks of symmetric cryptographic systems. They are used for S-box design in block ciphers and utilized as nonlinear filters and combiners in stream ciphers. To resist the known attacks on each cryptosystem, Boolean functions should satisfy various criteria simultaneously. In the framework of stream ciphers, the following criteria for cryptographic Boolean functions are mandatory:balancedness, large nonlinearity, high algebraic degree, high algebraic immunity, good behavior against fast algebraic attacks, good autocorrelation properties and high order resiliency. The high order resiliency is necessary for Boolean functions used in combiner models to allow resistance to correlation attacks (which do not work for filter models) and a first order resiliency is enough for functions used in filter models.In this thesis, we concentrate our works on the domains of cryptographic Boolean func-tions used in filter models. We made the following five contributions.Firstly, we give a method to construct balanced Boolean functions with strict avalanche criterion (SAC) property, high algebraic degree and very high nonlinearity. Compared with the known balanced Boolean functions with SAC property, the constructed functions possess the highest nonlinearity and the best global avalanche characteristics (GAC) property.Secondly, we slightly modify the Tu-Deng function to get a class of even-variable bal-anced Boolean functions. The new function has optimal algebraic immunity (under the as-sumption that the Tu-Deng Conjecture is true) and maximal algebraic degree. Specifically, the nonlinearity of the new function is dramatically increased to the best nonlinearity of the balanced Boolean functions.Next, we propose two constructions of 1-resilient Boolean functions in even numbers of variables. The first class of functions has at least almost optimal algebraic immunity (un-der the assumption that the Tu-Deng Conjecture is true), optimal algebraic degree, that is, meet the Siegenthaler’s bound, and very high nonlinearity. Compared with all the known constructed 1-resilient ones without considering the algebraic immunity, our functions have better nonlinearity. The functions in the second class have optimal algebraic immunity, op-timal algebraic degree and high lower bound on the nonlinearity. We check that, at least for small values of the number of variables, functions in this class have very good nonlinearity and also good immunity to fast algebraic attacks.Fourthly, we consider the algebraic immunity of balanced Boolean functions with SAC property. We first present a construction of balanced Boolean functions with SAC property by a slight modification of a known method for constructing Boolean functions with SAC prop-erty and consider the cryptographic properties of the constructed functions. Then we propose an infinite class of balanced functions with optimal algebraic immunity and SAC property in odd numbers of variables, and the algebraic degree and nonlinearity of the functions in this class are determined.Finally, we show lower bounds on the second-order nonlinearity of two subclasses of well-known bent functions. We first improve a known lower bound on the second-order non-linearity of the simplest partial spread bent functions, whose nonlinearity profile has been bounded by Claude Carlet. This improvement allows obtaining a better bound for the whole profile. We subsequently give a lower bound on the second-order nonlinearity of some infinite class of Maiorana-McFarland bent functions, which generalizes a result given by Gangopad-hyay et. al.