Information Technology Reference
In-Depth Information
On 3-to-1 and Power APN S-Boxes
Deepak Kumar Dalai
Applied Statistics Unit, Indian Statistical Institute,
203, B T Road, Calcutta 700 108, India
deepak r@isical.ac.in
Abstract.
Almost Perfect Nonlinear (APN) S-boxes are used in block
ciphers to prevent differential attacks. The non-evidence of permutation
APN S-box on even number of variables and the eciency of power
functions bring the importance of power APN S-boxes to use in block
ciphers. We present a special class of 3-to-1 S-box (named as S3-to-1
S-box) on even number of variables. The power APN S-boxes on even
number of variables fall in this class. Further, another important class of
APN functions
X
3
+
tr
(
X
9
) too falls in this class. We study some results
of S3-to-1 S-boxes. In another section we present a necessary condition
for power functions to be APN. Using this necessary condition we can
filter out some non-APN power functions. Specifically, if the number of
variables is multiple of small primes, then one can filter out many non-
APN functions.
Keywords:
S-box,
Power
Function,
APN
Function,
Differential
Cryptanalysis.
1
Introduction
We denote by
V
m
, the field
GF
(2
m
)ofall
m
-dimensional binary vectors. The
multi-output Boolean functions of the form
F
:
V
m
V
m
are used by many
block ciphers (e.g., AES, DES, RC6) for the confusion part of the round func-
tion, which are called as the substitution box (in short, S-box). Therefore, most
of the cryptanalytic techniques on block ciphers are based on the analysis of
cryptographic strengths of underlying S-boxes. Differential cryptanalysis is one
of the important techniques to verify the strength of S-box against differential
attack [2]. Differential attack can be applied successfully if the number of so-
lutions of
F
(
x
+
a
)+
F
(
x
)=
b
for
a
→
V
m
are non uniform. Hence, to
prevent differential attack the output derivative
F
(
x
+
a
)+
F
(
x
)
,a
=0
,b
∈
=0shouldbe
uniformly distributed. In the binary case the best that can be expected is that
half the values occur twice; the S-boxes satisfy this property are called Almost
Perfect Nonlinear (APN) S-boxes [7]. Apart from the application in cryptogra-
phy, the APN functions have great interests in the study of coding theory and
some other areas of telecommunications.
A substantial amount of this work was done when the author was in Project CODES,
INRIA, Rocquencourt, France as a postdoctoral researcher. The author is very much
thankful to INRIA for providing fund to work there.
