Linear Properties Of Cryptographic Functions And Its Applications

Linear and nonlinear functions have important and extensive applications in designand analysis of stream ciphers, block ciphers, hash functions and error-correcting codes.In order to obtain effective diffusion, namely, more bits of the output of a cipher couldbe affected by a bit of the input and the key, we need to construct linear transformationswith good diffusion. In order to resist differential cryptanalysis and linear cryptanalysis,filter functions and nonlinear combinatorial of stream ciphers, S-boxes of block ciphersand nonlinear components of hash functions are constructed by nonlinear functions. Atthe same time, the nonlinear functions play an important role in the coding theory, it canbe used to construct linear codes with good property. Perfect nonlinear functions are withhigh nonlinearity and become a focus point of many research. Now the research of perfectnonlinear functions are mainly focusing on constructions, equivalent classifications andapplications in the cryptography and coding theory.The main contributes and fruits of this thesis are outlined as follows:(1) We propose three constructions of linear transformation from (F_n~2)~4 to (F_n~2)~4 withbranch number 4 based on rotations and xors. Meanwhile, the involutional property isproved under some conditions.(2) Since the South Korean standard ARIA adopts a 16×16 involutional linear trans-formation with branch number 8 as the diffusion layer, it is immune to differential crypt-analysisandlinearcryptanalysis. WeapplyintegralcryptanalysistotheblockcipherARI-A. We find some 3-round integral distinguishers of ARIA, which may lead to possible at-tackson4, 5and6-roundARIA.Boththedataandtimecomplexitiesof4-roundattackare225; the data and time complexities of 5-round attack are 227.2 and 276.7, respectively; thedata and time complexities of 6-round attack are 2124.4 and 2172.4, respectively. Moreover,the 4 and 5-round attacks have the lowest data and time complexities compared to existingattacks on ARIA. Further we discuss how to avoid the integral attacks in the design of theblock cipher, our results show that the choice of linear transformation with optimal branchnumber cannot avoid integral attacks.(3) We summarize all the known perfect nonlinear functions, then we focus on aclass of perfect nonlinear binomials which was found by Helleseth in 2008. It is the first class of perfect nonlinear binomials which are composed with inequivalent monomials.We transform the class of perfect nonlinear binomials to another form, and give a conciseproof. Furthermore, the count of this function family is given by using the polynomialstheory over finite field.(4) We study the properties of the perfect nonlinear functions of monomials and theDO polynomials by the theory of finite fields. Based on the theory of quadratic forms,we determine the preimage distributions of the two kinds of perfect nonlinear functionsthrough a unified approach. Then we determine the weight distributions of two classes oflinear codes constructing from the perfect nonlinear functions of DO polynomials using aunified approach, based on the theory of quadratic forms and exponential sums.