The Relationship Between Propagation Characteristics
and Nonlinearity of Cryptographic Functions
Jennifer Seberry
(The University of Wollongong, Wollongong, NSW 2522, Australia
jennie@cs.uow.edu.au)
XianMo Zhang
(The University of Wollongong, Wollongong, NSW 2522, Australia
xianmo@cs.uow.edu.au)
Yuliang Zheng
(Monash University, Melbourne, VIC 3199, Australia
yzheng@fcit.monash.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,
Sboxes. 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 socalled Sboxes 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
oneway 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 nonquadratic).
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
satisfies the propagation criterion with respect to
all but a subset
then the nonlinearity of f
satisfies
is the maximum dimension
a linear subspace contained in
can achieve. We also show that 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 Two techniques are employed in the proofs of
our main results.
The first technique is in regard to the structure of
the set of vectors where
the function f does not satisfy the propagation criterion.
By considering
a linear subspace
with the maximum dimension
contained in
together with its complementary subspace,
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 wellknown 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. 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 WalshHadamard 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 to GF(2)
(or simply functions on ),
is the vector space of n tuples of elements from GF(2).
The truth table of a function f on
is a (0,1)sequence defined by
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. An affine function f on is a function
that takes the form of where
Furthermore f is called a linear function if c=0. Page 137
Definition 1.
The Hamming weight of a (0,1)sequence s, denoted by
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 Note that
the maximum nonlinearity of functions on
coincides with the covering radius of the first order
binary ReedMuller code RM(1,n) of length
which is bounded from above by
(see for instance [CKHFMS85]).
Hence
for any function on
Next we introduce the definition of propagation criterion. Definition 2.
Let f be a function on
We say that f satisfies f(x) is also called
the directional derivative of f in the direction .
The above definition for propagation criterion
is from [PLL91].
Further work on the topic can be found in [PGV91].
Note that the strict avalanche criterion (SAC) introduced by Webster and
Tavares [Web85],[WT86] is equivalent to the
propagation criterion of degree 1 and
that the perfect nonlinearity studied by Meier and Staffelbach [MS90]
is equivalent to the propagation criterion of degree n where n is the number
of the coordinates of the function. 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
A vector is called a
linear structure of f if is a constant. By definition,
the zero vector in is
a linear structure of all functions on
It is not hard to see that
the linear structures of a function f
form a linear subspace of
The dimension of the subspace 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 [Eve88]. A (1,1)matrix H of order m is called a Hadamard matrix
if is the transpose of H
and is the identity matrix of order m.
A SylvesterHadamard matrix of order , denoted by
is generated by the following recursive relation Let
be the i row of
By Lemma 2 of [SZZ94a],
is the sequence of a linear function
defined by the scalar product
where is the ith vector in
according to the ascending order. Page 138
Definition 4.
Let f be a function on
The WalshHadamard transform
of f is defined as where
is the scalar product of
namely,
is regarded as a realvalued function. The WalshHadamard 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 is the ith vector in
according to the ascending order ,
is the sequence of f
and is the SylvesterHadamard matrix of order Definition 5.
A function f on is called a bent function if
its WalshHadamard transform satisfies 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 exist only when n is even [Rot76].
Another important property of bent functions is
that they achieve the highest possible
nonlinearity
3 More on WalshHadamard transform and Nonlinearity
As the WalshHadamard 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
their componentwise 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 Page 139
Set the scalar product of is also called
the autocorrelation 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. Let
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 [Dil72]),
M can be decomposed into where is the ith row of , a SylvesterHadamard matrix of order 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 WienerKhintchine 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 rank of S is the maximum number of linearly independent vectors in S.
Note that when S forms a linear subspace of
its rank coincides with its dimension. The distance between two functions
can be expressed as
where are the sequences of
respectively.
(For a proof see for instance Lemma 6 of [SZZ94a].)
Immediately we have: Lemma 6.
The nonlinearity of a function f on can be calculated by where is the sequence of f and
are the rows of
namely, the sequences of the linear functions on Page 140
The next lemma regarding splitting
the power of 2 can be found in [SZZ94d] Lemma 7.
Let be a positive integer and where both
and are integers. Then
when n is even, and when n is odd. In the next section we examine
the distribution of the vectors in
4 Distribution of
Let f be a function on
Assume that f satisfies the propagation criterion with respect
to all but a subset
Note that always contains the zero vector 0.
Write Thus Set
Then f satisfies the propagation criterion with
respect to all vectors in Consider the set of vectors
Then is a linear subspace contained in
When is a linear subspace
for any nonzero vector in
We are particularly interested in linear subspaces
with the maximum dimension contained in
For convenience, denote by the maximum dimension
and by W a linear subspace in
that achieves the maximum dimension. Obviously, f is bent if and only if
and f does not satisfy the propagation criterion with
respect to any vector if and only if
The case when
is especially interesting. Now let U be a complementary subspace of W,
namely
Then each vector can be
uniquely expressed as
where and
As the dimension of W is
the dimension of U is equal to
Write Proposition 8.
Proof.
follows from the fact that
W is a subspace of
Next we consider Clearly, In addition, for any Assume for contradiction that
Then we have
In this case
must form a subspace of
This contradicts the definition that
W is a linear subspace with the maximum dimension in This completes the proof. The next corollary follows directly from the above proposition. Corollary 9.
The size of satisfies
and
hence the rank of is at least
where is the maximum dimension
a linear subspace in can achieve. Page 141
5 Relating Nonlinearity to Propagation Characteristics
We proceed to the discussion of the nonlinearity of f. The main difficulty lies in
finding a good approximation of
is the sequence of f and
is a row of First we assume that where W is a linear subspace
in
that achieves the maximum dimension
and
U is a complementary subspace 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. Recall that
where is the sequence of Since
is specialized as where is the sequence of f,
is the ith row of
and Q comprises the 0th, rows of
Note that Q is an matrix. Let 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. From the construction of
we can see that the row of
is an allone sequence of length
if
and a balanced (1,1)sequence of length Recall that
(see also Proposition 8).
There are two cases associated with
In the first case,
is the allone 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 Therefore we can write
where each is a (1,1)matrix of
order
It is important to note that
the top row of each is
the allone sequence,
while the rest are
balanced (1,1)sequences of length With we have Let be the allone sequence of length Then This causes Page 142
and Similarly, with we have Thus we have the following result: Lemma 10.
Assume that f, a function on
satisfies the propagation criterion with respect
to all but a subset of vectors in
Set
and let W be a linear subspace with the maximum dimension
in
and U be a complementary subspace of W.
Assume that W and U satisfy (5) and (6)
respectively.
Then for all
where
is the sequence of f and
each is a row of Lemma 10 can be viewed as a refinement of
Parseval's equation
It implies that
Therefore by Lemma 6 we have
So far we have assumed that
W and U satisfy (5) and (6)
respectively.
When this is not the case,
we can always find a nonsingular
matrix A whose entries are from GF(2)
such that
the subspaces 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 [SZZ94b]).
This shows that the following theorem is true. Theorem 11.
For any function on
the nonlinearity of f
satisfies
where is the maximum dimension of the linear
subspaces in Theorem 11 indicates that
the nonlinearity of a function
is determined by the maximum dimension
that a linear subspaces in can achieve,
but not by the size of In [SZZ94e], we have proved that
where t is the rank of
By Corollary 9, we have
This implies that
Thus Theorem 11
is an improvement to the result in [SZZ94e].
This improvement can be demonstrated by a concrete example.
In [SZZ94e],
the following function on Page 143
has been shown to satisfy the propagation criterion with respect
to all but the following fives vectors in The rank t of is equal to 3.
By using the result of [SZZ94e],
On the other hand,
we can set
W is a fourdimensional subspace in Using Theorem 11 with =4, we have
(Note that according to [CKHFMS85],
the maximum nonlinearity a function on can achieve is 12.
Hence we have )
6 A Tight Lower Bound on Nonlinearity of Functions with Propagation Characteristics
By Theorem 11, 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. Theorem 12.
If f, a function on
satisfies the propagation criterion with respect to
one or more vectors in
then the nonlinearity of f satisfies
Proof.
As in the previous sections,
we denote by 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 subspace
in that achieves the maximum dimension By Theorem 11,
the theorem is trivially true when
Next we consider the case when
We prove this part by further refining
the Parseval's equation. As in the proof of Lemma 10,
without loss of generality, we can assume that Similarly to Lemma 10, we have where is the sequence of f and is a row of Comparing the first row of (2), we have or equivalently, Page 144
where each
is the first row of the matrix M described in (2). Rewrite the ith row of
where is the binary representation of an integer i
in the ascending alphabetical order.
Set N is a symmetric matrix of order with integer entries.
In [Rot76],
Rothaus has shown that
We can split N into four submatrices of equal size,
namely where each is a matrix of order
As
we have Let be an
arbitrary linear sequence of length Then is a linear sequence of length
and hence a row of
Thus from (11), we have Hence Rewrite the left hand side of (12) as where As
is a linear sequence, Hence (13) can be written as Page 145
Since This proves that (13) is equal to zero and
hence By Lemma 7, Since is an arbitrary
linear sequence of length and each linear sequence of length is a column of from (14) we have where Therefore Recall that a matrix A of order s is said to be orthogonal if It is easy to verify that is an orthogonal matrix. Thus On the other hand, by (10) we have Hence Now let denote the ith row of
where is the binary representation of From (15), Note that Page 146
Thus where is on the ith position of the column vector. Write Then As we have From (16), (17) and (18) and hence where i is an arbitrary integer in
Similarly, holds for all
By Lemma 6, the nonlinearity of f satisfies This completes the proof. As an immediate consequence, we have Corollary 13.
Let f be a function on Then the following statements hold: Page 147
Finally we show that
the lower bound 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 [SZZ94c]).
f satisfies the propagation criterion
with respect to
all vectors in whose first two bits are nonzero,
which count for three quarters of the vectors in
It is not hard to verify that is the linear subspace that achieves the maximum dimension Thus we have a result described as follows: Lemma 14.
The lower bound as stated in Theorem 12 is tight.
7 Conclusion
We have shown quantitative relationships
between
nonlinearity, propagation characteristics and the SAC.
A tight lower bound on the nonlinearity of
a function with propagation characteristics
is also presented. This research has also introduced a number of
interesting problems yet to be resolved.
One of the problems is regarding the
size and distribution of
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. Acknowledgments We would like to thank the anonymous referees for their
helpful comments.
The first author was supported in part by
the Australian Research Council (ARC)
under the reference numbers
A49130102, A49131885 and A49232172,
and
by the Australian Telecommunications and Electronics Research Board (ATERB)
under the reference number C010/058,
the second author by
ARC A49130102
and ATERB C010/058,
and the third author
by ARC A49232172 and ATERB N069/412.
All authors were supported by
a University of Wollongong Research Program grant. This work was done while the third author
was with the University of Wollongong.
References
[AT90]
C. M. Adams and S. E. Tavares.
Generating and counting binary bent sequences.
IEEE Transactions on Information Theory, IT36 No.
5:11701173, 1990. Page 148
[Bea84]
K. G. Beauchamp.
Applications of Walsh and Related Functions with an Introduction
to Sequency Functions.
Microelectronics and Signal Processing. Academic Press, London, New
York, Tokyo, 1984.
[BKPS93]
L. Brown, M. Kwan, J. Pieprzyk, and J. Seberry.
Improving resistance to differential cryptanalysis and the redesign
of LOKI.
In Advances in
Cryptology  ASIACRYPT'91,
Lecture Notes in Computer Science,
vol. 739,
pp. 650,
SpringerVerlag, Berlin, New York, Tokyo, 1993.
[CKHFMS85]
G. D. Cohen, M. G. Karpovsky, Jr. H. F. Mattson, and J. R. Schatz.
Covering radius  survey and recent results.
IEEE Transactions on Information Theory, IT31(3):328343,
1985.
[Dil72]
J. F. Dillon.
A survey of bent functions.
The NSA Technical Journal, pp. 191215, 1972.
(unclassified).
[Eve88]
J.H. Evertse.
Linear structures in blockciphers.
In Advances in Cryptology  EUROCRYPT'87,
Lecture Notes in Computer Science,
vol. 304, pp. 249266,
SpringerVerlag, Berlin, Heidelberg, New York, 1988.
[Lai92]
X. Lai.
On the Design and Security of Block Ciphers.
ETH Series in Information Processing. HartungGorre Verlag Konstanz,
Zuerich, 1992.
[LaSM91]
X. Lai and J. L. Massey ans S. Murphy.
Markov ciphers and differential cryptanalysis.
In D. W. Davies, editor, Advances in Cryptology  EUROCRYPT'91,
Lecture Notes in Computer Science,
vol. 547,
pp. 1738,
SpringerVerlag, Berlin, New York, Tokyo, 1991.
[LM91]
X. Lai and J. L. Massey.
A proposal for a new block encryption standard.
In I. B. Damgard, editor, Advances in Cryptology 
EUROCRYPT'90,
Lecture Notes in Computer Science,
vol. 473,
pp. 389404,
SpringerVerlag, Berlin, New York, Tokyo, 1991.
[Miy91]
S. Miyaguchi.
The FEAL cipher family.
In Advances in Cryptology  CRYPTO'90,
Lecture Notes in Computer Science,
vol. 537,
pp. 627638,
SpringerVerlag, Berlin, New York, Tokyo, 1991.
[MS77]
F. J. MacWilliams and N. J. A. Sloane.
The Theory of ErrorCorrecting Codes.
NorthHolland, Amsterdam, New York, Oxford, 1977.
[MS90]
W. Meier and O. Staffelbach.
Nonlinearity criteria for cryptographic functions.
In Advances in Cryptology  EUROCRYPT'89,
Lecture Notes in Computer Science,
vol. 434,
pp. 549562,
SpringerVerlag, Berlin, Heidelberg, New York, 1990.
[NBS77]
National Bureau of Standards.
Data encryption standard.
Federal Information Processing Standards Publication FIPS PUB 46,
U.S. Department of Commerce, January 1977.
[NIST93]
National Institute of Standards and Technology.
Secure hash standard.
Federal Information Processing Standards Publication FIPS PUB 180,
U.S. Department of Commerce, May 1993.
[PGV91]
B. Preneel, R. Govaerts, and J. Vandewalle.
Boolean functions satisfying higher order propagation criteria.
In Advances in Cryptology  EUROCRYPT'91,
Lecture Notes in Computer Science,
vol. 547,
pp. 141152,
SpringerVerlag, Berlin, Heidelberg, New York, 1991.
[PLL91]
B. Preneel, W. V. Leekwijck, L. V. Linden, R. Govaerts, and J. Vandewalle.
Propagation characteristics of boolean functions.
In Advances in Cryptology  EUROCRYPT'90,
Lecture Notes in Computer Science,
vol. 437,
pp. 155165,
SpringerVerlag, Berlin, Heidelberg, New York, 1991.
[Riv92]
R. Rivest.
The MD5 message digest algorithm, April 1992.
Request for Comments (RFC) 1321.
[Rot76]
O. S. Rothaus.
On ``bent'' functions.
Journal of Combinatorial Theory, Ser. A, 20:300305, 1976.
[SZZ94a]
J. Seberry, X. M. Zhang, and Y. Zheng.
Nonlinearity and propagation characteristics of balanced boolean
functions.
To appear in Information Page 149
and Computation, 1994.
[SZZ94b]
J. Seberry, X. M. Zhang, and Y. Zheng.
Nonlinearly balanced boolean functions and their propagation
characteristics.
In Advances in Cryptology  CRYPTO'93,
Lecture Notes in Computer Science,
vol. 773,
pp. 4960,
SpringerVerlag, Berlin, Heidelberg, New York, 1994.
[SZZ94c]
J. Seberry, X. M. Zhang, and Y. Zheng.
On constructions and nonlinearity of correlation immune functions.
In Advances in Cryptology  EUROCRYPT'93,
Lecture Notes in Computer Science,
vol. 765,
pp. 181199,
SpringerVerlag, Berlin, Heidelberg, New York, 1994.
[SZZ94d]
J. Seberry, X. M. Zhang, and Y. Zheng.
Relationships among nonlinearity criteria.
Presented at EUROCRYPT'94, 1994.
[SZZ94e]
J. Seberry, X. M. Zhang, and Y. Zheng.
Structures of cryptographic functions with strong avalanche
characteristics.
Presented at ASIACRYPT'94, 1994.
[Web85]
A. F. Webster.
Plaintext/ciphertext bit dependencies in cryptographic system.
Master's Thesis, Department of Electrical Engineering, Queen's
University, Ontario, Cannada, 1985.
[WT86]
A. F. Webster and S. E. Tavares.
On the design of Sboxes.
In Advances in Cryptology  CRYPTO'85,
Lecture Notes in Computer Science,
vol. 219,
pp. 523534,
SpringerVerlag, Berlin, Heidelberg, New York, 1986.
[YH89]
R. Yarlagadda and J. E. Hershey.
Analysis and synthesis of bent sequences.
IEE Proceedings (Part E), 136:112123, 1989.
[ZPS93]
Y. Zheng, J. Pieprzyk, and J. Seberry.
HAVAL  a oneway hashing algorithm with varialbe length of
output.
In Advances in Cryptology  AUSCRYPT'92,
Lecture Notes in Computer Science,
vol. 718,
pp. 83104,
SpringerVerlag, Berlin, New York, Tokyo, 1993. Page 150
