Cryptography Reference
In-Depth Information
Clearly,
δ
can be computed by a naive computation as shown in Algorithm 1.
It needs time
O
(2
2
n
). Note that the bias
δ
as computed by Algorithm 1 can be
expressed by
2
n
a
1)
f
1
(
a
)
b
1
1)
f
2
(
b
)
D
(
a
δ
=
(
−
(
−
⊕
b
)
.
(1)
Define functions
g
1
,g
2
:
GF
(2)
n
→{
1
,
−
1
}
as follows
1)
f
1
(
x
)
g
1
(
x
)=(
−
(2)
1)
f
2
(
x
)
g
2
(
x
)=(
−
(3)
We can rewrite Eq.(1) by
2
n
a
1
δ
=
g
1
(
a
)
·
g
2
(
b
)
·
D
(
a
⊕
b
)
(4)
b
2
n
a
1
=
g
1
(
a
)
·
(
g
2
⊗ D
)(
a
)
(5)
1
2
n
(
g
1
⊗
=
g
2
⊗
D
)(0)
(6)
where
denotes the convolution. As convolution can be computed eciently by
Fast Walsh Transform (FWT), we finally have proved the following result.
Theorem 1.
Given
f
1
,f
2
:
GF
(2)
n
⊗
→ GF
(2)
and a distribution
D
over
GF
(2)
n
,
assuming that the uniformly distributed
n
-bit
a, b
satisfy that
a, a ⊕ b
are inde-
pendent and that
a
⊕
b
complies with the given distribution
D
, the bias
δ
of
f
1
(
a
)
⊕
f
2
(
b
)
can be expressed by
2
2
n
x
1
· D
(
x
)
,
δ
=
g
1
(
x
)
·
g
2
(
x
)
F
(
x
)=
y
(
where the Walsh Transform
F
of
F
is defined by
1)
x·y
F
(
y
)
and
−
g
1
,g
2
are defined in Eq.(2), Eq.(3) respectively.
Note that it needs
O
(
n
2
n
) time to compute
δ
by above theorem, while it
needs
O
(2
n
) time to compute
δ
under the independence assumption by Piling-
up lemma. Moreover, Theorem 1 can be easily generalized to the following result.
×
Corollary 1.
Given
f
1
,f
2
,...,f
k
:
GF
(2)
n
GF
(2)
and a distribution
D
over
GF
(2)
n
, assuming that the uniformly distributed
n
-bit
a
1
,a
2
,...,a
k
→
satisfy that
a
1
,...,a
k−
1
,a
1
⊕···⊕
a
k
are independent and that
a
1
⊕···⊕
a
k
complies with
the given distribution
D
, the bias
δ
of
f
1
(
a
1
)
⊕···⊕
f
k
(
a
k
)
can be expressed by
2
kn
x
1
· D
(
x
)
,
δ
=
g
1
(
x
)
·
g
2
(
x
)
···
g
k
(
x
)
1)
f
i
(
x
)
where
g
i
(
x
)=(
−
for
i
=1
,...,k
.
Search WWH ::
Custom Search