On Cryptographic Properties Of Boolean Functions

Cryptographic Boolean functions have wide application in stream ciphers and blockciphers. This dissertation investigates the basic theory of Boolean function; concludessome properties of Boolean functions. The author obtains main results as follows:(1). The result of GAC which is derived by Son is analyzed. A lower bound on thesum-of-squares of any Boolean functions with Hamming weight k is concluded, theexpression of upper bound on nonlinearity with Hamming weight k is given. Thetwo constructions which has the lower absolute criterion and the lower sum of squarecriterion from Bent functions is obtained.(2). To measure the correlative degree between two Boolean functions, based on GAC,the sum-of-squares indicator and the absolute indicator of cross-correlation are pro-posed. The two indicators improve the GAC criterion (which proposed by X.M.Zhang and Y.L. Zheng). Lower and upper bounds on the two indicators are ob-tained, and some properties between Walsh spectrum and cross-correlation func-tions are given.(3). Some properties of Boolean functions with linear structure are presented. By themethods of Walsh transform and the Hamming weight, a su?cient condition on aBoolean function without k linear structure is derived. An upper bound on nonlin-earity of a resilient function with linear structure is deduced by these results.(4). Based on the definition of algebraic thickness, some relationships of algebraicthickness are derived. The upper bound on algebraic thickness of affine Booleanfunctions,correlation immunity,Bent functions,partially Bent functions andplateaued functions are at most 2^n-1. According to this fact an upper bound onalgebraic thickness of elementary symmetric Boolean functions of n variables withalgebraic degree k(2≤k≤n-1/2 ) is improved.(5). Based on the theory of subspace, a sufficient and necessary condition on whethera Boolean function is normal or not is obtained. A relationship between the Ham-ming weight of Boolean function and the dimension k of a given affine subspace isdiscussed. Furthermore, an algorithm to check whether a given Boolean function isk-normal is given, this algorithm is better than the method which is used for theenumeration of all k-dimensional affine subspaces.(6). By Krawtchouk polynomial and combinatorial Mathematics, some properties ofthe equal-weight symmetric Boolean functions are discussed. The Walsh spectra of the equal-weight symmetric Boolean functions is given. Some cryptographic prop-erties(including nonlinearity, correlative immunity, PC and balanced) are obtained,these results implies that the equal-weight symmetric Boolean function is bad forcryptographic properties.