2752

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 50, NO. 11, NOVEMBER 2004

Almost Security of Cryptographic Boolean Functions
Kaoru Kurosawa, Member, IEEE, and Ryutaroh Matsumoto, Member, IEEE()

Abstract—The propagation criterion, PCof order , is oneof the most general cryptographic criteria of secure Boolean functions . In this paper, we formalize its -almost version. The new
definition requires thatis almost uniformly
distributed while in the original definition, it must be strictly uniformly distributed. Better parameters are then obtained than thestrict PCof order functions. To construct -almost PCoforder functions, we introduce a notion of domain distance.

( ) + ( + 1)()()
Index Terms—Boolean functions, -almost version, PC ( ) oforder .

I. INTRODUCTION
A. Overview

S

EVERAL criteria of Boolean functions have been developed to examine their cryptographic properties. However,the properties have shown to be contradictory in the sense thatstrict fulfillment in one criterion leads to less optimal fulfillment
or complete failure with respect to another criterion. Previously,
Kurosawa, Johansson, and Stinson introduced the notion of -almost -resilience [9], which relaxes, in a controlled manner, thestrict requirement of -resilience.
The goal of this paper is to extend this approach to the propaof order . That is, we formalize an -algation criterion PC
of order . The new definition requires
most version of PC
is almost uniformly distributed while inthat
the original definition, it must be strictly uniformly distributed.
Better parameters are then obtained than the strict PC of orderfunctions. To construct -almost PC of order functions,
we introduce a notion of domain distance.
B. PC

of Orderand its Almost Version

PC of order [19], [20] is one of the most general criteria
among many cryptographic criteria which have been studied inorder to design secure block ciphers.
is said to satisfy PC if the output
A Boolean function
differenceis uniformly distributed for any, wheredenotes
input difference withsatisfies
the Hamming weight of . Further suppose thatare fixed into any
PC even if any bits ofconstants. Then we say thatsatisfies PC of order .
The famous strict avalanche criterion (SAC), which was introduced as a criterion of the security of S-boxes [21], is equivManuscript received May 19, 2003; revised June 9, 2004.
K. Kurosawa is with the Department of Computer and Information Sciences,
Ibaraki University 4-12-1 Nakanarusawa, Hitachi, Ibaraki, 316-8511, Japan(e-mail: kurosawa@cis.ibaraki.ac.jp).
R. Matsumoto is with the Department of Communications and Integrated
Systems, Tokyo Institute of Technology, 2-12-1 O-okayama, Meguro-ku, Tokyo
152-8552, Japan (e-mail: ryutaroh@it.ss.titech.ac.jp).
Communicated by T. Johansson, Associate Editor for Complexity and
Cryptography.
Digital Object Identifier 10.1109/TIT.2004.836684

is equivalent to PC of order . Also,
alent to PC . SAC
is a bent function [11, Ch. 14] if and only ifsatisfies[19], where a bent function has the largest distance fromPC
the set of affine (linear) functions. (Hence, it is directly related
to the linear attack.) PC of order in general is directly related to the security against differential attacks.
ofKurosawa et al. gave a general method to design PC
order functions by using linear codes [10]. Carlet extended it
to nonlinear codes [4].
Boolean functions, however, do not need to satisfy the strict
definitions of cryptographic criteria in general. These definitions
are sometimes stronger than what we want and may introduce
other vulnerabilities. For example, cryptographic Boolean functions need to be balanced, but bent functions are never balanced.
Therefore, it would be good if by relaxing the conditions, betterparameters with respect to all known attacks could be obtained.
From this point of view, this paper introduces a notion of -alof order . It requires thatismost PCalmost uniformly distributed while in the original definition, it
must be strictly uniformly distributed. We then show that indeedof orderbetter parameters are obtained than the strict PC
functions.
of orderWe present a design method of -almost PC
functions using linear codes and an -biased sample spaces [13]which satisfy some property. To achieve our goal, we introduce a
new notion of domain distance. Our construction offers smaller
input length than the strict PC of order functions for the. (The input size of S-boxes can be smaller for thesamesecurity level.) In other words, we can obtain larger
for the same input length . (Higher security levelcan beobtained for the same input size of S-boxes.)of order functions
We also show that our -almost PCof ahave large nonlinearity, where the nonlinearity
Boolean function is defined by a distance between andmust be large to avoid linear
the set of affine functions.
attack.
We finally generalize our result to multiple output bit Booleanfunctions.
Remark 1.1: We compare our construction of -almost
PC of order with the strict PC of order functions using
linear codes [10] because it is the best known construction.
It will be further work to show that for any strict PC
oforder function, there exists a better -almost PC of orderfunction.
C. Related Work
Suppose that
tributed even if any bits ofstant. We then say that is an0018-9448/04$20.00 © 2004 IEEEis uniformly disare fixed into any con-resilient function. This

KUROSAWA AND MATSUMOTO: ALMOST SECURITY OF CRYPTOGRAPHIC BOOLEAN FUNCTIONS

notion has been studied by several researchers from the point ofview of key renewal [6], [2], [8], [17], [3], [18]. Especially, a notion of -almost -resilient functions was introduced in [9]. The
authors presented its construction and showed that better parameters are obtained than the strict -resilient functions. Dodis etal. improved it by showing a probabilistic construction [7].
Our work can be considered as an extension of [9]. Indeed,of order function is obit is shown that an -almost PC
tained from a linear code and an -almost -resilient function
with a special property. The special property is characterizedby our new notion of domain distance. We then present how toconstruct such -almost -resilient functions by extending thetechnique of [9].
D. Organization
This paper is organized as follows. Section II is for preliminaries. In Section III, we review almost resilient functions.
of orderSection IV formalizes a notion of -almost PC
functions and shows our basic theorem. Our construction ispresented in Section V. Section VI shows a comparison withof order functions.
our construction with the strict PC
In Section VII, we study the nonlinearity of our construction.
Section VIII shows a generalization to multiple-output bits. In
Section IX, we discuss -systematic almost -wise independent
sample spaces.
II. PRELIMINARIES
We use to denote a Boolean function, andto denote a function, where. We
use to denote, where is a binary variable.
the Hamming weight of a binary vector
We denote by. Let denote the inner product of two binary vectors overdenotes the cardinality of .
GF . For a set ,Let a linear-code denote a binary linear code oflength , dimension , and the minimum Hamming distance atof a linear code is defined as
least . The dual code
for all. The dual minimum Hammingof is defined as the minimum Hamming distancedistance.
of
A. Resilient Functions
Definition 2.1: We say that
-resilient function if
tributed even if any variables
constants. That is,. Then each is a linear
Proof: Let. Further, each linear function has
function ofor more nonzero coefficients.
Now it is known thatis anresilient function if and only if
(1)
is an

-resilient function for any. (See [6].) In our case, expression (1) becomes thefollowing:where. Note that

becauseto see thatis a nonzero codeword of . Then it is easyis -resilient.
Q.E.D.

We say that
-resilient function.
B. PC

is -resilient if

is anof OrderDefine the derivative of
for

by

.

Definition 2.2: [19], [20] We say that a Boolean function
satisfies PC of order if
is -resilientwith. (We also say thatfor any
is a PC of order function.)
Kurosawa et al. gave a general method to design PC
order functions by using two linear codes [10].

ofProposition 2.2: Suppose that there exist-codewith the dual minimum1) a linear
andHamming distance at least-codewith the dual minimum2) a linear.
Hamming distance at leastof order function
Then there exists a PC
such that.
III. ALMOST RESILIENT FUNCTIONS

is an
is uniformly disare fixed into any

for any

positions, for any -bit string
and for any fixed, where() are chosen independently at
the values
random.

Chor et al. showed that an
obtained from a linear

2753-resilient function can be-code [6].

Proposition 2.1: Letbe a generator matrix of a linear-code . Thenis an-resilient function.

A. Almost -Wise Independent Sample Space. An -biased sample
Let be a constant such thatspace is a subset
which looks random. To foris anbinarymalize this notion, we consider thatmatrix and each row is randomly chosen.
Definition 3.1:

for any
sample space.

is -biased if. We also say thatis an -biased

An almost -wise independent sample space is a subset
such that any out of bits look random. To formalize
this notion, we consider thatis anbinary matrix
and each row is randomly chosen.

2754IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 50, NO. 11, NOVEMBER 2004

Definition 3.2: (Almost -wise independence). Suppose thatis chosen randomly from. Then we say thatis-independent if for any positions
and any -bit string , we have

(We also say thatspace.)

is an almost -wise independent sample

It is known that a large almost -wise independent sample
space
can be obtained from a small -biased sample space, where.
Proposition 3.1: [13] Suppose thata parity-check matrix of a
Defineis -biased. Let be-linear code .

is-independent, where

Kurosawa, Johansson, and Stinson introduced a notion of-almost -resilient functions [9]. It is an -almost version of-resilient functions.
Definition 3.3: [9] We say that
-almost-resilient function if

positions, and for any fixed

the values
random.

is a -almost.
IV. ALMOST PC-resilient function with
Q.E.D.
OF ORDER

In this section, we formalize a notion of -almost PCoforder functions. It is an -almost version of PC of orderfunctions.

Definition 4.1: We say thatsatisis an -alfies -almost PC of order if its derivative
most-resilient function for any
with. (We also say thatis an -almost PCoforder function.)
The definitions of ”PC of order ” and ” -almost PC
order ” are summarized in Table I.

B. Almost Resilient Functions

for any

Then

A. Definition
(2)

Then

TABLE I
DEFINITIONS OF PC(`) AND "-ALMOST PC(`)

is an, for any-bit string, whereare chosen independently at

The authors presented its construction by using -systematic-independent sample spaces [9].
Definition 3.4: [9] An-independent sample spaceis called -systematic if, and there exist positions
such that each -bit string occurs in these positions.
for exactly one -tuple in-systematic -biased sample spaces are defined similarly.
Proposition 3.2: [9, Theorem 4.4] If there exists a -sys-independent sample space, then there exists
tematic-resilient function , wherea balanced -almost.
Proof Sketch: Without loss of generality, assume that
positions in
run through all possible -bit
the first
sample spaces
indexed bystrings. We construct
byFinally, define a function
if and only ifby the rule
(3)ofB. Basic Theorem
We show that an almost PC of order function is obtained
from a linear code and an -almost-resilient function
which satisfies some property. We first introduce a notion of
domain distance.
andDefinition 4.2: For a function, define
for any

For nonempty, letbe the minimum Hamming distanceof the code
. Then we define the domain distanceof bywhere the minimum is taken over all nonempty.

Lemma 4.1: Suppose that a function
has the domain distance . Thenfor anyif
Proof: Suppose that.

for some

,
, and
with
. Then, whereis the minimum. This is a contradiction.
Q.E.D.
Hamming distance ofWe next prove the following lemma.

Lemma 4.2: Let
be an -almost-resilient function with. Thenis a-almost-resilient function for any, where.
, let
Proof: For any

KUROSAWA AND MATSUMOTO: ALMOST SECURITY OF CRYPTOGRAPHIC BOOLEAN FUNCTIONS

Then. Therefore,

2755

TABLE IIRELATIONSHIP BETWEEN PROPOSITION 2.2 AND THEOREM 4.1

Similarly, we have
C. Discussion

Hence,

Similarly
Q.E.D.
Then our basic theorem is stated as follows.
Theorem 4.1: Suppose that there exist
1) a linear-codewith the dual minimum
andHamming distance at least2) an -almost-resilient function with the do.
main distanceof order function
Then there exists a -almost PC
such thatand.
be a generator matrix of. Define a
Proof: LetwithasBoolean function
and
, let
follows. For
(4)
where
satisfiesthatthe derivative of by

Equation (4) gives a general formula of our -almost PC
of order function. Note that Proposition 2.2 can be seen as acorollary of Theorem 4.1.
, whereis a generator
Indeed, in (4), let-code. Thenis anmatrix of a linear-resilient function from Proposition 2.1. In this case,is equal to the dual minimum
it is easy to see that theHamming distance of .
The relationship between Proposition 2.2 and Theorem 4.1 issummarized in Table II.
-code with
Now suppose that there exists a linear. In what
the dual minimum Hamming distance at least-refollows, we show that there exists an -almost
silient function with the domain distance at least
such that.
This means that we can obtain smaller input length for the. In other words, we can obtain larger
for thesame
same .

is any Boolean function. We show
-almost PC of order . Define

V. CONSTRUCTION
A. Outline

Then

Case 1. Suppose that
case

and

Then
because. Hence,of-resilient from Lemma 4.2.
andCase 2. Suppose that
Then for any
where
a constant. Now. In thisis not a codeword
is-almost.

isbecause. Therefore,is-resilient from the proof of Proposition 2.1.
This means thatis -resilient.
satisfies-almost PC
ofConsequently,
Q.E.D.
order .

From the proof of Theorem 4.1, we can construct a-almost PC
of orderfunctionby using a-codewith the dual minimum Hamming
lineardistance at least
and an -almost-resilient.
function with the domain distanceIn this section, we show how to achieve the second condition,-resilient function
i.e., how to construct an -almost
with the domain distance at least.
-independent
We define the domain distance of anas follows.
sample space
Definition 5.1: For an-independent sample space,
be a nonlinear code such that each row ofisleta codeword. Then we say thathas the domain distance ,.
where is the minimum Hamming distance of
It is easy to see that the domain distanceof defined.
by (3) is equal to the minimum Hamming distance of
Therefore, it is reasonable to define the domain distance of an-independent sample space
as above.
Now our construction is outlined as follows.
Step 1. We first show that the second condition of
Theo- rem 4.1 is satisfied if there exists a -sys-independent sample spacewhose
tematic.
domain distance is at least

2756

Step 2.

Step 3.

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 50, NO. 11, NOVEMBER 2004

We next show that suchis obtained from a-systematic -biased sample space
and a linear-code with the dual minimum
Hamming distance at least.
by using
We finally show how to construct such
Weil–Carlitz–Uchiyama bound. (The same technique-inwas used in [9] to construct a -systematic
dependent sample space
directly.)

Proposition 5.1: (Weil–Carlitz–Uchiyama Bound) [11,Ch. 9, Theorem 19] Let
GF
be a polynomial such that
GF
polynomialThenand for any constantfor any.

B. Step 1–Step 3
We show Step 1–Step 3 of the previous subsection.
Theorem 5.1: Suppose that there exists a -systematic-independent sample spacewith the domain dis. Then there exists a balanced -almost
tance at least-resilient function with the domain distanceat least, where.
as shown in the proof of
Proof: Construct from
Proposition 3.2. Then the is a balanced -almost-resilient function.
Next suppose that
. That is,forand such that
. Then we see that
some
and

is an odd degree
for anyandNow for two positive integers and
, let
and
. Let
be a primitive element of GF
andbe the elements of GF. For eachGF
, let
be a string of length
such that

whereThis means that there are two codewords with the distance or. However, this is a contradiction because
has theless indomain distance at least.
Q.E.D.
Theorem 5.2: Suppose that there exists a -systematic -biand a linear-code
ased sample spacewith the dual minimum Hamming distance at least. Then-independent sample space
there exists a -systematicwith the domain distance at least, whereProof: Letis thewhere

Remark 5.1: It is easy to see that if
polynomial, thenany .

be a parity-check matrix of
identity matrix. Let

The proposed -biased sample space is defined as
..
.

(6)

Theorem 5.3: The above-biased sample space such thatis a -systematic
and,Proof: First it is a well known fact [9, p. 245] that
(5)

Then

is

-independent from Proposition 3.1, where

Next it is easy to see thatis -systematic ifis-systematic.
has the domain distance at least
Finally, we show that
. From (5), we see thatis a subset of all codewordsof. Therefore,
has the domain distance at least
because has the dual distance at least.
Q.E.D.
We next show how to construct a -systematic -biased
by using Weil–Carlitz–Uchiyama bound. For
sample space
GF
, let

It is well-known that
.

or

and

runs through-systematic.
Next consider

whenruns through GF
. Let

where

Then since

is binary, we have that

. HenceisKUROSAWA AND MATSUMOTO: ALMOST SECURITY OF CRYPTOGRAPHIC BOOLEAN FUNCTIONS

where

Since

2757

Balanced -almost
the domain distanceis a primitive element,

at least-resilient function, wherewith

Q.E.D.

if and only if
We finally obtain the following corollary.

This implies thatNow define

because.

Let

Corollary 5.2: Suppose that there exist-codewith the dual minimum1) a linear
andHamming distance at least-codewith the dual
2) a linear.
minimum Hamming distance at least
Then there exists a -almost PC
of orderfunctionsuch that
andThen we see that

Proof: From Theorem 4.1 and Corollary 5.1. It is illustrated as follows.
Linear-code
with the dual distanceat least.
Finally, from the Weil–Carlitz–Uchiyama bound (see also
Remark 5.1), we have

(Corollary 5.1)
Balanced -almost
domain distance at least-resilient function with the, whereHence,
Q.E.D.

Linear-code
with the dual minimum.
Hamming distance at least( Theorem 4.1)

C. Final Construction
Corollary 5.1: Suppose there exists a linear-code with the dual distance at least. Then there-resilient function withexists a balanced -almost
such thatthe domain distance at least

Proof: From Theorems 5.1, 5.2, and 5.3. More precisely,
it is illustrated as follows.
-systematic -biased sample spacesuch that
and(Theorem 5.3 )-almost PC
where

Finally, by letting
corollary.

of order function
and

and

,

, we obtain this
Q.E.D.

To summarize, a -almost PC of order function is constructed as follows.
1) Construct a -systematic -biased sample spacewithby using Theorem 5.3, where

Linear-code with the dual minimum.
Hamming distance at least2) LetTheorem 5.2-systematic-independent sample space, wheredomain distance at least

Theorem 5.1.

with thebe a parity-check matrix of a linear-codewith the dual minimum Hamming distanceat least. Define. Thenis a -sys-independent sample space with the domain
tematic
from Theorem 5.2, where
distance at least

2758

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 50, NO. 11, NOVEMBER 2004

3) From, construct a balanced -almost
silient function with the domain distanceby using Theorem 5.1, where

4) Letcode
least-reat least

be a generator matrix of a linearwith the dual minimum Hamming distance at. Define

whose generator polynomial
has as a root, whereis a primitive element of GF. Then we obtain a linear-code [11, p. 204]. Its dual codeis also a cyclic
code such that the generator polynomial
has as a root
[16, p. 227, eq. (2.10)]. Therefore, the parity-check matrix ofincludes a row of[11, p. 203, eq (19)]. Thishas
as a codeword.
means that
Let the basis ofbe, whereDefinewhereis any Boolean function.
is a -almost PC
of order function
Thenfrom Corollary 5.2, where the input length is
and

VI. COMPARISON
Proposition 2.2 can be seen as a corollary of Corollary 5.2.
Indeed, letin Corollary 5.2. Then we obtain
Proposition 2.2.
Now let us compare the parameters of -almost PC of orderfunctions (Corollary 5.2) with the strict PC of order functions (Proposition 2.2).
• In Proposition 2.2, the dimension ofis equal to .
is equal to• In Corollary 5.2, the dimension of.
because. Hence,.
Therefore,
This shows that our construction has a smaller input length. In other words, our construction has larger
for the samefor the same input length . (From Corollary 5.2, we canalso see that the larger is, the smaller both andare.)
As an example, first try to construct a PCof order function by using Proposition 2.2 from a linear
code
which has the dual minimum Hamming distance at. Then from Proposition 2.2, weleast . Suppose thatneed a linear-code . However, it is clear
forand. Hence we cannot construct
thatof order function for
and
.
a PC
Next consider to construct -almost a PCof order function by using Corollary 5.2 for the same
and
.
and
in Corollary 5.2. Then we see that a
Let
-code
with the dual minimum Hamming
lineardistance at least is necessary.
As shown below, there exists a linear
-code
with
the dual minimum Hamming distance at least . Hence, we canconstruct a -almost PC
of order function with the input, wherelengthfor, where is a binary vector of length . Let be a
are the basis of . Then is alinear code such that-code which includes
as a codeword.
linearof the dual
It implies that the minimum Hamming distancecode
is even. That is,.
VII. ON OTHER CRYPTOGRAPHIC CRITERIA
To simplify the notation, letCorollary 5.2. Then our -almost PC
is written as

andof orderinfunction(7)

from (4), where•and;is an -almost-resilient•
function with the domain distance;is a generator matrix of a linear-code•with the dual minimum Hamming distance at least;is any Boolean function.
•
A. Balance
We say thatis balanced if

In this subsection, we show that ourappropriately in (7).

is balanced if

is chosen

Definition 7.1: For , define

We say thatis balanced for

if
(8)
(9)

Theorem 7.1: Our is balanced if is balanced forinto (7), where
Proof: Substituteconstant. Then we havein (7).
is a(10)

We finally show that there exists a linear-code.
Consider a Bose–Chaudhuri–Hocquenghem (BCH) code

Case 1. If, then the right-hand side of(10) is a nonconstant affine function on . In thiscase,is balanced as a function on .

KUROSAWA AND MATSUMOTO: ALMOST SECURITY OF CRYPTOGRAPHIC BOOLEAN FUNCTIONS

Case 2. If, then we have

2759

Then

In this case,for a half ofandfor the half ofbecause is balanced for .
The above argument implies thatis balanced.

Q.E.D.

We show that it is easy to find a which is balanced for . A
trivial way is to write down the truth table of .
Another way is as follows. From the proofs of Theorem 5.1
if and only
and Proposition 3.2, we see that
. Therefore,, whereif
is a -systematic-independent sample space. Assume thatthe first positions in
run through all possible -bit strings.
Define by

Then it is easy to see that

becausewhereis an affine function and is a bent function,. Therefore,

is balanced for .

B. Nonlinearity
Define a distance between two Boolean functions
byandThe nonlinearity of a Boolean function , denoted by, isdefined by a distance between and the set of affine functions

because.
odd, letIf
and definethat

becauseRemark 7.1: For, define

where

be a bent function. Then we obtain.

Q.E.D.
andis an affine function.
must be large to avoid linear attack.
In this subsection, we show that our has large nonlinearity, it
if is chosen appropriately in (7). For
holds that [15], [12]and. Thenis a-resilient function for any
if the Hamming weight ofis strictly greater than for[5, Sec.2.1]. Carlet studied the nonlinearity ofanythis type of resilient functions in [5].

If the equality is satisfied, then is called a bent function. Thereeven [15], [12].
exists a bent function if and only if

Equation (7) can be expressed similarly to the preceding. However, we cannot
equation by letting
apply the result of Carlet [5] because it is possible thatfor somein (7).

Theorem 7.2: In Corollary 5.2, let
the -almost PC
of order function
has nonlinearity such thatand

. Thenwhere

VIII. GENERALIZATION TO MULTIPLE-OUTPUT BITS
if
if

even
odd

where
and is given in Corollary 5.2.
Proof: Remember that is expressed by (7).
If
, let
be a bent function.
and an affine
We compute the distance between thisas follows. For, definefunctionIn this section, we generalize our result to multiple-output
Boolean functions.
Definition 8.1: We say that
-almost PC of order if
PC of order for any

satisfies
satisfies -almost.

Theorem 8.1: Suppose that there exist
1) a linear-codewith the dual minimum
andHamming distance at least-codewith the dual
2) a linear
minimum Hamming distance at least

2760

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 50, NO. 11, NOVEMBER 2004

Then there exists a -almost PC
such thatof order function, wherewhere GF

. Let
..
.

Proof: Letbe a generator matrix of a linear-codewith the dual minimum Hamming distance at
least
. Let
be an -almost-resilient function.
with the domain distancewith
Consider a linear feedback shift register of lengtha primitive feedback polynomial. Let be the state transition
matrix of such a shift register. Let
and
. For
, define
whereis any Boolean function. Then we show thatsatisfies-almost PCoforder .
ForThen

is a -systematic.

-independent sample space with
Q.E.D.

The above
can be constructed as follows. Fora fixed (odd) degree , we can express each polynomial as alinear combination of

The polynomials in this set are clearly independent over GF
asIndexing the polynomials in
we obtain a binary
matrix, where.

, we have..
.

It is easy to see thatis a permutation, as pointed out by Nyberg [14]. Therefore,of the space
this matrix is nonsingular. It implies thatis a generator matrix of the linear code . Thenfrom the proof of Theorem 4.1, we see thatsatisfies-almost PC of order .
The rest of the proof is straightforward from Section V.
Q.E.D.
IX. ON -SYSTEMATIC ALMOST -WISE INDEPENDENTSAMPLE SPACEIn this section, we discuss on the previous construction of-systematic almost -wise independent sample spaces [9].
A. Previous Construction
Kurosawa, Johansson, and Stinson showed a construction of-systematic-independent sample spaces[9] as follows.
Definition 9.1: A polynomial
GF
is called a-polynomial if has degree at most andforall even , where. Defineto be-polynomials such that any polynomials in thea set ofset are independent over GF .

..

..

.

.

..
.

where
. Any
polynomials are independent over GF
means that any
columns of the above matrix are linearly independent. Hence,
the matrix corresponds to a parity-check matrix of anerror-correcting code, a code of length,, and minimum Hamming distancedimension[11].
In order to get a -systematic sample space, we have already.
chosen the polynomials
But clearly, this is no restriction, since any parity-check matrix
can be rewritten into such a form without changing the code
parameters.
B. RelationshipWe show that the previous
coincides with ourignore the condition on the domain distance. Let

if we

Then
(11)
From (11), it is easy to see that

Proposition 9.1: Suppose that is a primitive element of, andis chosen such that
GF
Then there exists a -systematic-independent sample
space
where
and
.
. ConProof Sketch: Let
as follows: A binary string
struct a sample spaceis specified by

Therefore, by letting
..
.

(12)

we obtain that(13)

KUROSAWA AND MATSUMOTO: ALMOST SECURITY OF CRYPTOGRAPHIC BOOLEAN FUNCTIONS

Here (13) is the same as (2), and (12) is equivalent to (6).
Therefore, we can see that the previous construction coincides
with our construction if we ignore the condition on the domain
distance.
C. On the Domain Distance
However, it is essential thathas the domain distance atin the construction of -almost PC
of orderleast
functions. In the previous method [9],is constructed directly
from. From that point of view, we have no idea.
on how to impose the domain distance condition on
On the other hand, ouris constructed from the equation. From this point of view, it is very easy to impose
the condition on the domain distance through . Indeed, it isenough that is a parity-check matrix of a linear code with the.
dual minimum Hamming distance st least
In [9], it was not shown that theis an -biased sample
space, neither.

REFERENCES[1] N. Alon, O. Goldreich, J. Hastad, and R. Peralta, “Simple constructionsof almost k -wise independent random variables,” Random Structures
and Algorithms, vol. 3, pp. 289–304, 1992.
[2] C. H. Bennett, G. Brassard, and J.-M. Robert, “Privacy amplification by
public discussion,” SIAM J. Comput., vol. 17, pp. 210–229, 1988.
[3] J. Bierbrauer, K. Gopalakrishnan, and D. R. Stinson, “Bounds for resilient functions and orthogonal arrays,” in Proc. CRYPTO ’94 (Lecture
Notes in Computer Science). Berlin, Germany: Springer-Verlag, 1994,
vol. 839, pp. 247–257.
[4] C. Carlet, “On the propagation criterion of degree l and order k ,” in Advances in Cryptology—Proc. EUROCRYPT ’98 (Lecture Notes in Computer Science). Berlin, Germany: Springer-Verlag, 1998, vol. 1403,
pp. 462–474.
, “A larger class of cryptographic boolean functions via a[5]
study of the Maiorana-McFarland construction,” in Advances in Cryptology—Proc. CRYPTO’02 (Lecture Notes in Computer Science). Berlin, Germany: Springer-Verlag, 2002, vol. 2442, pp. 549–564.

2761[6] B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich, and R.
Smolensky, “The bit extraction problem or t-resilient functions,” inProc. 26th IEEE Symp. Foundations of Computer Science, 1985, pp.
396–407.
[7] Y. Dodis, A. Sahai, and A. Smith, “On perfect and adaptive security
in exposure-resilient cryptography,” in Proc. EUROCRYPT ’01 (Lecture
Notes in Computer Science). Berlin, Germany: Springer-Verlag, 2001,
vol. 2045, pp. 301–324.
[8] J. Friedman, “On the bit extraction problem,” in Proc. 33rd IEEE Symp.
Foundations of Computer Science, 1992, pp. 314–319.
[9] K. Kurosawa, T. Johansson, and D. Stinson, “Almost k -wise independent sample spaces and their cryptologic applications,” J. Cryptol., vol.
14, no. 4, pp. 231–253, 2001.
[10] K. Kurosawa and T. Satoh, “Design of SAC/PC (l) of order k Booleanfunctions and three other cryptographic criteria,” in Advances in
Cryptology—Proc. EUROCRYPT ’97 (Lecture Notes in Computer
Science). Berlin, Germany: Springer-Verlag, 1997, vol. 1233, pp.
434–449.
[11] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting
Codes: North-Holland, 1977.
[12] W. Meier and O. Staffelbach, “Nonlinearity criteria for cryptographic
functions,” in Advances in Cryptology—Proc. EUROCRYPT ’89 (Lecture Notes in Computer Science). Berlin, Germany: Springer-Verlag,
1990, vol. 434, , pp. 549–562.
[13] J. Naor and M. Naor, “Small bias probability spaces: Efficient constructions and applications,” SIAM J. Comput., vol. 22, pp. 838–856, 1993.
[14] K. Nyberg, “Perfect nonlinear S-boxes,” in Advances in Cryptology—
Proc. EUROCRYPT ’91 (Lecture Notes in Computer Science). Berlin,
Germany: Springer-Verlag, 1991, vol. 547, , pp. 378–386.
[15] O. S. Rothaus, “On bent functions,” J. Comb. Theory (A), vol. 20, pp.
300–305, 1976.
[16] H. Stichtenoth, Algebraic Function Fields and Codes. Berlin, Germany: Springer-Verlag, 1993.
[17] D. R. Stinson, “Resilient functions and large set of orthogonal arrays,”
Congr. Numer., vol. 92, pp. 105–110, 1993.
[18] D. R. Stinson and J. L. Massey, “An infinite class of counterexamples toa conjecture concerning nonlinear resilient functions,” J. Cryptol., vol.
8, pp. 167–173, 1995.
[19] B. Preneel, W. Van Leekwijck, L. Van Linden, R. Govaerts, and J.
Vandewalle, “Propagation characteristics of boolean functions,” inAdvances in Cryptology—Proc. EUROCRYPT ’90 (Lecture Notes in
Computer Science). Berlin, Germany: Springer-Verlag, 1991, vol.
473, , pp. 161–173.
[20] B. Preneel, R. Govaerts, and J. Vandewalle, “Boolean functions
satisfying higher order propagation criteria,” in Advances in Cryptology—Proc. EUROCRYPT ’91 (Lecture Notes in Computer Science),
1991, vol. 547, pp. 141–152.
[21] A. F. Webster and S. E. Tavares, “On the design of S-boxes,” in Advances in Cryptology—Proc.CRYPTO ’85 (Lecture Notes in Computer
Science). Berlin, Germany: Springer-Verlag, 1986, vol. 218, pp.
523–534.