The Propagation Characteristics Of Boolean Functions

B.Preneel et al. generalized the Perfect Nonlinearity Criterion and the Strict Avalanche Criterion and put forward the Propagation Criterion of degree k , PC( k ). Because of the important application of the propagation criterion in cryptology, especially in block cipher, the properties and constructions of Boolean functions satisfying PC( k ), SAC(m), PC(k)/m or EPC(k)/m have been an important research field in cryptology theory. In addition, Boolean permutation plays an important role in designing cryptology system. A cryptology system without any information expansion can be regarded as a permutation. Therefore constructions of Boolean permutation with high degree and high nonlinearity have become an important study problem.This paper has studied Propagation Criterion of Boolean functions and Boolean permutation and has gained results as following:1) In the first chapter, the main study achievements and results of Boolean functions satisfying propagation criterion have been summarized.2) In the first section of the second chapter, the propagation properties of Boolean functions have been studied. A sufficient and necessary condition on which a Boolean function satisfies propagation criterion is given. And the propagation property of joint Boolean function is studied. The fact that Boolean functions f(x) which satisfy PC(k) is globally invariant under the transformation of "weight kept" is proved. A sufficient condition on which Boolean function satisfy PC( k ) is presented.When g(x1,...,x_h) = 0 or x1...x_h, the sufficient and necessary condition on which f(x1.... ,x_n ) satisfies PC( k ) is given.3) In the second section of the second chapter, the relationship of Boolean permutation and propagation properties is studied. By the Boolean permutation, the sufficient and necessary condition on which Boolean functions with high degrees satisfy PC(n) is derived. And Boolean functions satisfying SAC are constructed under the transformation of Boolean permutation. In addition, a new method to construct Boolean permutation is brought forward. In the end, thealgorithm and program calculating the Boolean permutation(x0...x_n-1^2n-2 are given.