Cryptography Reference
In-Depth Information
4.5
Exercises
p
q
we define
Exercise 4.1.
Given a function f
:
{
0
,
1
}
→{
0
,
1
}
DP
f
(
a
,
b
)
=
Pr[
f
(
X
+
a
)
=
f
(
X
)
+
b
]
LP
f
(
a
1)
2
,
b
)
=
(2 Pr[
a
·
X
=
b
·
f
(
X
)]
−
p
. Give an algorithm for computing the whole
where X is uniformly distributed in
{
0
,
1
}
table of
DP
f
in O
(2
p
+
q
)
steps.
7
Give an algorithm for computing the whole table of
LP
f
+
q
)2
p
+
q
)
steps.
in O
((
p
Exercise 4.2.
Prove that if f
:
{
0
,
1
}
p
→{
0
,
1
}
q
, the following bounds hold.
Bound
Name of eq. case
Necessary condition for eq.
DP
f
max
≥
2
−
q
PN
p
≥
2
q
,
p even
DP
f
max
≥
2
1
−
p
APN
p
≤
qor
(
p
,
q
)
=
(2
,
1)
LP
f
max
≥
2
−
p
B
p
≥
2
q
,
p even
LP
f
max
≥
u
(
p
,
q
)
AB
p
=
q
,
p odd
where
2
1
−
p
1
(2
q
−
p
1)(2
p
−
1
−
−
1)
u
(
p
,
q
)
=
+
.
2
q
−
1
Equality cases are called Perfect Nonlinear (PN), Almost Perfect Nonlinear (APN),
Bent (B), and Almost Bent (AB). In addition, prove that B is equivalent to PN and that
AB is equivalent to APN.
8
Exercise 4.3.
We define
f
: GF(2
33
)
32
→{
0
,
1
}
linear mapping
g
: GF(2
33
)
GF(2
33
)
x
3
→
=
g
(
x
)
32
GF(2
33
)
{
,
}
→
E
:
0
1
linear mapping
where f consists of discarding 1 bit, and E is injective, and
F
K
(
x
)
=
f
(
g
(
E
(
x
)
+
K
))
7
This
O
notation means that there exists a constant
c
>
0 such that for any
p
and
q
, the complexity of
this algorithm is at most
c
2
p
+
q
elementary operations. The notion of complexity is formally defined in
Chapter 8.
8
This exercise was inspired by Ref. [44].
Search WWH ::
Custom Search