Information Technology Reference
In-Depth Information
Note 2.
1
,m
)=1foreach
m
. Hence, we do
not learn any information. For example, we can not say anything about
X
3
,X
13
,X
25
,X
27
etc.
2. If
a
q
>
1and
m
is prime then gcd(
a
q
−
1. If
a
q
=2thengcd(
a
q
−
1
,m
) = 1. Hence, no information in
this case. For example, we can not say anything about
X
11
in
V
7
,V
11
etc.
3. If
m
is Mersenne prime (i.e., 2
m
1 is also prime) then all gcd functions in
the conditions return 1 except when
d
= 1. Thus, we can say something only
for linear functions (i.e.,
X
2
i
).
4. If
m
is a multiple of small primes then we can filter out many
X
d
's as non-
APN because the chance of co-primeness with
m
and 2
m
−
1 decreases.
5. There are some
X
d
's, which can not be filtered using the necessary condition
but
X
e
,e
=2
l
d
mod (2
m
−
1) for some
l>
0 may satisfy the conditions and
can be shown as non-APN. In this case,
X
d
−
can too be filtered out. For
example,
X
13
can not be shown as non-APN directly in
V
4
but
X
7
can be
used to show
X
13
as non-APN because 13 = (2
2
7) mod 15 and
X
7
∗
is
non-APN according to Theorem 5.
We have an interesting fact that we can filter out some power S-boxes
X
d
,
gcd(
d,
2
m
1) = 3 when
m
is even and gcd(
d,
2
m
1) = 1 when
m
is odd. In
Table 4, we present two types of comparision on the number of filtered S-boxes
for both the even and odd number of variable cases. In first tuple, we compare the
number
X
d
s that can be filtered out from the total 2
m
−
−
2 non-constant power
functions. In second tuple, we compare the number of filtered power functions
from the total number of power functions satisfying gcd(
d,
2
m
−
−
1) = 3 when
m
is even and gcd(
d,
2
m
1) = 1 when
m
is odd. In some cases, specifically when
m
is a multiple of small primes, we can filter out a big percentage of non-APN
functions using our necessary conditions. However, using the necessary condition
in Theorem 5 and the observation in Note 5 we can filter out some
X
d
's which
are not APN. Therefore, while searching for a good APN S-box, one can simply
discard those functions and save some searching time.
−
Acknowledgment.
The author is very much thankful to Prof. Pascale Charpin
for her excellent guidance and suggestions that provided me to gain the ideas
and to improve the quality of this paper.
References
1. Berger, T.P., Canteaut, A., Charpin, P., Laigle-Chapuy, Y.: Almost Perfect Nonlin-
ear functions. IEEE Trans. Inform. Theory 52(9), 4160-4170 (2006)
2. Biham, E., Shamir, A.: Differential Cryptanalysis of DES-like Cryptosystem. Jour-
nal of Cryptology 4(1), 3-72 (1991)
3. Budaghyan, L., Carlet, C., Leander, G.: Constructing new APN functions from
known ones. Cryptology ePrint Archive: report 2007/063
4. Carlet, C., Charpin, P., Zinoviev, V.: Codes, Bent Functions and Permutations
Suitable For DES-like Cryptosystems. Des. Codes Cryptogr. 15(2), 125-156 (1998)
5. Charpin, P., Tietavamen, A., Zinoviev, V.: On binary cyclic codes with minimum
distance
d
= 3. Problems Inform. Transmission 33(4), 287-296 (1997)
