On Relevance of Nonlinearity, Derivative, and E-Derivative for Boolean Functions
In this paper, we discuss the impact of weight structure of the derivative and e-derivative on the nonlinearity of Boolean functions, and the relationship among the nonlinearity, derivative, and e-derivative of Boolean functions. And get six kinds of relations among nonlinearity, derivative, and e-derivative of Boolean functions. The methods to solve the nonlinearity are derived based on those relationships, thus solving the problem that it’s difficult to calculate the nonlinearity only in accordance with the definition. Introduction The properties of Boolean functions, such as the nature linear complexity, the nonlinearity [2], the proliferation, correlation immunity, algebraic immunity and so on, are necessary properties to resist a variety of cryptography password attacks [1~5]. Looking for Boolean functions with a variety of high index cryptographic properties of Boolean functions are cryptographic properties of the important research work task. The high nonlinearity of Boolean functions is important properties of affine cryptosystem resist attack. High nonlinearity of Boolean functions of existence and other issues are also important work [6~8]. The nonlinearity of Boolean function is a nonlinear index to measure the resistance of a password system to an affine approximation attack. The higher the nonlinearity of Boolean functions, the stronger the ability to resist the affine approximation attacks [6~7]. The nonlinearity of Boolean functions f N has always been defined by the definition ( ) [ ] min ( ( ) ( )) n f t l x L x N w f x l x ∈ = + , which requires us to find a linear function 0 ( ) l x through the collection [ ] n L x of 2 n linear functions, so 0 ( ( ) ( )) f t N w f x l x = + can be satisfied. But it is tough to find 0 ( ) l x [8]. On the study of cryptography properties of Boolean functions, the main research methods [1~8] we take are as follows, such as the methods of algebraic analysis, spectral analysis, matrix analysis, weighting analysis, linear subspace analysis and cascade analysis. Using these methods, we analyze the whole values of Boolean functions, but cannot differentiate values of Boolean functions’ two different properties. Therefore we cannot find the relation between values of Boolean functions’ two different properties and properties of Boolean functions. The derivative of Boolean function, also known as difference, was proposed long ago. The derivative of Boolean function doesn’t play a significant role when it is used alone in studying the properties of Boolean functions. So we cannot find the trace of the derivative of Boolean function in studying the properties of Boolean functions. Using the derivative of Boolean function expresses the values of one property of Boolean functions, and the values of another property of Boolean functions can be reflected by the e-derivative which defined by ourselves. Using the derivative and the e-derivative as main research tools to study the cryptographic properties of Boolean functions, we can reveal the relation between values of Boolean functions’ two different properties and properties of Boolean functions. So we will find more useful results through researching properties of Boolean functions from a broad and sufficient view. The Boolean function is formed by its derivative and its e-derivative [9~10]. This paper reveals the impacts of the derivative and e-derivative on the nonlinearity of Boolean functions, through respectively discussing the relationship of the linear function, derivative and e-derivative of Boolean functions. At the same time, the method to calculate 0 ( ) l x with the derivative and ederivative is gotten, so f N can also be solved. So the hard-solved calculation of the nonlinearity of Boolean functions has got its solution. Preliminaries The Boolean functions of cryptographic are defined on Galois field (2) GF , i.e. (2) 1 2 ( ) ( , , , ) (2) n GF n f x f x x x GF = ∈ . In this paper, we discuss cryptographic properties of H Boolean functions on (2) GF . To study cryptographic properties of H Boolean functions, we proposed the concept of the e-derivative. The e-derivative [9~10] and derivative [11] are defined here as Definition 1&2. Definition 1: The e-derivative (e-partial derivative) of n-dimensional Boolean functions (2) 1 2 ( ) ( , , , ) (2) n GF n f x f x x x GF = ∈ for r variables 1 2 , , , i i ir x x x is defined as