| Submission Procedure |
|
|
|
|||||||||||||||
The Relationship Between Propagation Characteristics and Nonlinearity of Cryptographic Functions
(The University of Wollongong, Wollongong, NSW 2522, Australia jennie@cs.uow.edu.au)
Abstract: The connections among the various nonlinearity criteria is currently an important topic in the area of designing and analyzing cryptographic functions. In this paper we show a quantitative relationship between propagation characteristics and nonlinearity, two critical indicators of the cryptographic strength of a Boolean function. We also present a tight lower bound on the nonlinearity of a cryptographic function that has propagation characteristics. Keywords: Cryptography, Boolean functions, Encryption functions, Nonlinearity, Propagation Characteristics, SAC, S-boxes. Category: E.3 1 Introduction
Data Encryption Standard or DES is a cryptographic algorithm most widely used by industrial, financial and commercial sectors all over the world [NBS77]. DES is also the root of many other data encryption algorithms proposed in the past decade, including LOKI [BKPS93], FEAL [Miy91] and IDEA [LM91][LaSM91][Lai92]. A core component of these encryption algorithms are the so-called S-boxes or substitution boxes, each essentially a tuple of nonlinear Boolean functions. In most cases, these boxes are the only nonlinear component in an underlying encryption algorithm. The same can be said with one-way hashing algorithms which are commonly employed in the process of signing and authenticating electronic messages [ZPS93][Riv92][NIST93]. These all indicate the vital importance of the design and analysis of nonlinear cryptographic Boolean functions. Encryption and authentication require cryptographic (Boolean) functions with a number of critical properties that distinguish them from linear (or affine) functions. Among these properties are high nonlinearity, high degree of propagation, few linear structures, high algebraic degree etc. These properties are often called nonlinearity criteria. An important topic is to investigate relationships among the various nonlinearity criteria. Progress in this direction has been made Page 136 in [SZZ94d], where connections have been revealed among the strict avalanche characteristic, differential characteristics, linear structures and nonlinearity, of quadratic functions. In this paper we carry on the investigation initiated in [SZZ94d] and bring together nonlinearity and propagation characteristic of a function (quadratic or non-quadratic). These two cryptographic criteria are seemly quite separate, in the sense that the former indicates the minimum distance between a Boolean function and all the affine functions whereas the latter forecasts the avalanche behavior of the function when some input bits to the function are complemented. In particular we show that
if f, a function on We also show that Two techniques are employed in the proofs of
our main results.
The first technique is in regard to the structure of
The organization of the rest of the paper is as follows: Section 2 introduces basic notations and conventions, while Section 3 presents background information on the Walsh-Hadamard transform. The distribution of vectors where the propagation criterion is not satisfied is discussed in Section 4. This result is employed in Section 5 where a quantitative relationship between nonlinearity and propagation characteristics is derived. This relationship is further developed in Section 6 to identify a tight lower bound on nonlinearity of functions with propagation characteristics. The paper is closed by some concluding remarks in Section 7. 2 Basic Definitions
We consider Boolean functions from An affine function f on Page 137 Definition 1.
The Hamming weight of a (0,1)-sequence s, denoted by Note that
the maximum nonlinearity of functions on Definition 2.
Let f be a function on
f(x) While the propagation characteristic measures the avalanche effect of a function, the linear structure is a concept that in a sense complements the former, namely, it indicates the straightness of a function. Definition 3.
Let f be a function on By definition,
the zero vector in A (1,-1)-matrix H of order m is called a Hadamard matrix
if
Let Page 138 Definition 4.
Let f be a function on
where The Walsh-Hadamard transform, also called the discrete Fourier transform, has numerous applications in areas ranging from physical science to communications engineering. It appears in several slightly different forms [Rot76],[MS77],[Dil72]. The above definition follows the line in [Rot76]. It can be equivalently written as
where Definition 5.
A function f on
for all Bent functions can be characterized in various ways [AT90],[Dil72],[SZZ94a],[YH89]. In particular the following four statements are equivalent:
Bent functions on 3 More on Walsh-Hadamard transform and Nonlinearity
As the Walsh-Hadamard transform plays a key role in the proofs of main results to be described in the following sections, this section provides some background knowledge on the transform. More information regarding the transform can be found in [MS77],[Dil72]. In addition, Beauchamp's book [Bea84] is a good source of information on other related orthogonal transforms with their applications. Given two sequences Page 139 Set
the scalar product of Let
where Clearly
On the other hand, we always have
where Comparing the two sides of (3), we have
Equivalently we write
In engineering, (4) is better known as (a special form of) the Wiener-Khintchine Theorem [Bea84]. A closely related result is Parseval's equation (Corollary 3, p. 416 of [MS77])
which also holds for any function f on Let S be a set of vectors in The distance between two functions
can be expressed as Lemma 6.
The nonlinearity of a function f on
where Page 140 The next lemma regarding splitting the power of 2 can be found in [SZZ94d] Lemma 7.
Let In the next section we examine
the distribution of the vectors in 4 Distribution of |
|||||||||||||||||
satisfies the propagation criterion with respect to
all but a subset 
then the nonlinearity of f
satisfies 
is the maximum dimension
a linear sub-space contained in 
can achieve.
is the tight lower bound
on the nonlinearity of f if f satisfies
the propagation criterion with respect to
at least one vector in 
As an immediate consequence,
the nonlinearity of a function that fulfills the
SAC or strict avalanche criterion is
at least 
the set of vectors where
the function f does not satisfy the propagation criterion.
By considering
a linear sub-space
with the maximum dimension
contained in 
together with its complementary sub-space,
we will be able to identify how the vectors in 
are distributed.
The second technique is based on
a novel idea of refining
Parseval's equation, a well-known relationship
in the theory of orthogonal transforms.
A combination of these two techniques
together with some careful analyses
proves to be a powerful tool
in examining the relationship
among nonlinearity criteria.
to GF(2)
(or simply functions on 
and the sequence of f
is a (1,-1)-sequence defined by 
The matrix of f is a (1,-1)-matrix of order 
defined by 
f is said to be balanced if its truth table contains an equal number of
ones and zeros.
is a function
that takes the form of 
where 
Furthermore f is called a linear function if c=0.
is the number of ones in the sequence.
Given two functions f and g on 
the Hamming distance d(f,g)
between them is defined as
the Hamming weight of the truth table of
f(x)
g(x),
where 
d.
The nonlinearity of f, denoted by
is the minimal Hamming distance
between f and all affine functions on 
are all the affine functions on
coincides with the covering radius of the first order
binary Reed-Muller code RM(1,n) of length
which is bounded from above by 
(see for instance [
for any function on
Next we introduce the definition of propagation criterion.
is also called
the directional derivative of f in the direction 
.
The above definition for propagation criterion
is from [
A vector 
is called a
linear structure of f if 
is a constant.
is
a linear structure of all functions on 
The dimension of the sub-space is called
the linearity dimension of f.
We note that it was Evertse
who first introduced the notion of linear structure
(in a sense broader than ours)
and studied its implication on
the security of encryption algorithms [
is the transpose of H
and 
is the identity matrix of order m.
A Sylvester-Hadamard matrix of order 
, denoted by 
is generated by the following recursive relation
be the i row of 
By Lemma 2 of [
is the sequence of a linear function 
defined by the scalar product
where 
is the ith vector in 
according to the ascending order.
The Walsh-Hadamard transform
of f is defined as
is the scalar product of 
namely
,
is regarded as a real-valued function.
is the ith vector in 
according to the ascending order 
,
is the sequence of f
and
is the Sylvester-Hadamard matrix of order
is called a bent function if
its Walsh-Hadamard transform satisfies
exist only when n is even [
their component-wise product is defined by 
Let f be a function on 
For a vector 
denote by 
the sequence of 
Thus 
is the sequence of f itself
and 
is the sequence of 
is also called
the auto-correlation of f with a shift 
.
Obviously, 
if and only if 
is balanced,
i.e., f satisfies the propagation criterion with respect to 
On the other hand, if 
is a constant
and hence 
is a linear structure of f.
be the matrix of f and 
be the sequence of f.
Due to a very pretty result by R. L. McFarland
(cf. Theorem 3.3 of [
is the ith row of 
, a Sylvester-Hadamard matrix of order 
its rank coincides with its dimension.
where 
are the sequences of 
respectively.
(For a proof see for instance Lemma 6 of [
can be calculated by
is the sequence of f and
are the rows of 
namely, the sequences of the linear functions on 
be a positive integer and 
where both
and 
are integers. Then 
when n is even, and 
when n is odd.
Assume that f satisfies the propagation criterion with respect
to all but a subset 
Note that 
always contains the zero vector 0.
Write 
Thus 
Then f satisfies the propagation criterion with
respect to all vectors in 
Then 
is a linear sub-space contained in 
When 
is a linear sub-space
for any nonzero vector in 
We are particularly interested in linear sub-spaces
with the maximum dimension contained in 
For convenience, denote by 
the maximum dimension
and by W a linear sub-space in 
that achieves the maximum dimension.
and f does not satisfy the propagation criterion with
respect to any vector if and only if 
The case when 
is especially interesting.
Then each vector 
can be
uniquely expressed as 
where 
and 
As the dimension of W is 
the dimension of U is equal to 
Write 
follows from the fact that
W is a sub-space of 
Next we consider 
Assume for contradiction that
Then we have 
In this case 
must form a sub-space of 
This contradicts the definition that
W is a linear sub-space with the maximum dimension in 
This completes the proof.
satisfies
and
hence the rank of 
is at least 
where 
is the maximum dimension
a linear sub-space in 
can achieve.
is the sequence of f and
is a row of 
that achieves the maximum dimension 
and
U is a complementary sub-space of W.
The more general case where
(5) or (6) is not satisfied
can be dealt with after employing
a nonsingular transform on the input of f.
This will be discussed in the later part of this section.
where 
is the sequence of 
Since 
is specialized as
is the sequence of f,
is the ith row of 
and Q comprises the 0th, 
rows of 
Note that Q is an 
matrix.
be the 
row of 
where 
Note that 
can be uniquely expressed as 
where 
and 
.
Let 
be the 
row of 
and
be the 
row of 
As
can be represented by 
where 
denotes the Kronecker product.
row of 
is an all-one sequence of length
if
and a balanced (1,-1)-sequence of length 
(see also Proposition 8).
There are two cases associated with 
In the first case, 
is the all-one sequence of length 
while in the second case,
we have 
which implies that
is a balanced (1,-1)-sequence of length 
and hence 
is a concatenation of 
balanced (1,-1)-sequences of length 
where each 
is a (1,-1)-matrix of
order 
It is important to note that
the top row of each 
is
the all-one sequence,
while the rest are
balanced (1,-1)-sequences of length 
we have
be the all-one sequence of length 
Then
we have
satisfies the propagation criterion with respect
to all but a subset 
of vectors in 
Set 
and let W be a linear sub-space with the maximum dimension 
in 
and U be a complementary sub-space of W.
Assume that W and U satisfy (5) and (6)
respectively.
Then
where
is the sequence of f and
each 
is a row of 
It implies that 
Therefore by Lemma 6 we have 
matrix A whose entries are from GF(2)
such that
the sub-spaces W' and U' associated with
f'(x) = f(x A) have the required forms.
f' and f have the same algebraic degree
and nonlinearity (see Lemma 10 of [
the nonlinearity of f
satisfies 
where 
is the maximum dimension of the linear
sub-spaces in 
can achieve,
but not by the size of 
where t is the rank of 
By Corollary 9, we have 
This implies that 
Thus Theorem 11
is an improvement to the result in [
is equal to 3.
By using the result of [
On the other hand,
we can set 
W is a four-dimensional sub-space in 
=4, we have 
(Note that according to [
can achieve is 12.
Hence we have 
)
if f, a function on 
satisfies the propagation criterion
with respect to at least one vector in 
This section shows that this lower bound can be significantly improved.
Indeed we prove that 
and also show that it is tight.
satisfies the propagation criterion with respect to
one or more vectors in 
then the nonlinearity of f satisfies 
the set of vectors in 
with respect to which the propagation criterion
is not satisfied by f.
We also let 
and W be a linear sub-space
in 
that achieves the maximum dimension 
Next we consider the case when 
We prove this part by further refining
the Parseval's equation.
is the sequence of f and 
is a row of 
is the first row of the matrix M described in (2).
the ith row of 
where 
is the binary representation of an integer i
in the ascending alphabetical order.
Set
with integer entries.
In [
We can split N into four sub-matrices of equal size,
namely
is a matrix of order 
As
we have 
be an
arbitrary linear sequence of length 
and hence a row of 
Thus from (11), we have
is a linear sequence, 
is an arbitrary
linear sequence of length 
and each linear sequence of length 
is a column of 
from (14) we have
Therefore
It is easy to verify that 
is an orthogonal matrix. Thus
denote the ith row of 
where 
is the binary representation of
From (15),
is on the ith position of the column vector.
Then
we have
Similarly,
By Lemma 6, the nonlinearity of f satisfies
Then the following statements hold:
is tight.
We achieve the goal
by demonstrating a function on 
whose nonlinearity
is equal to 
Let 
be
a function on 
Then the nonlinearity of g is 
Now let
be
a function on 
Then the nonlinearity of f is 
(see for instance Lemma 8 of [
whose first two bits are nonzero,
which count for three quarters of the vectors in 
It is not hard to verify that
Thus we have a result described as follows:
as stated in Theorem 12 is tight.
the set of vectors where the propagation criterion
is satisfied by a function on 
For all the functions we know of,
is either an empty set
or a set with at least 
vectors.
We believe that
any further understanding of this problem
will contribute to
the research into
the design and analysis of
cryptographically strong
nonlinear functions.
