Cryptography Reference
In-Depth Information
Computation circuit
Mask circuit
a
a
X
Y
⊕
⊕
a
a
·
Z
=(
a
·
X
)
⊕
(
a
·
Y
)
Z
Z
=
X
⊕
Y
Figure 4.5.
Dual circuit of a XOR gate.
over the uniform distribution of
X
. In a second step, we collect many (
x
i
,
f
(
x
i
)) pairs
for
i
N
and we use the biased Boolean information in order to recover some
statistical information.
=
1
,...,
Let us start with a few preliminaries.
q
is described by a circuit
which contains only substitution boxes, XOR gates, key gates, and duplicate gates. The
circuit is an acyclic directed graph which can be represented into layers such that all gate
inputs in some layer
i
are outputs from gates in layer
i
p
to
We assume that a keyed function
f
from
{
0
,
1
}
{
0
,
1
}
1. Layer 1 includes
p
input bits
of
f
and key gates. The last layer includes
q
output bits of
f
. Starting from the output of
f
, we consider
b
−
f
(
x
). This means that we consider a bit mask
b
applied to the last layer
of the circuit. This mask indicates which output bits from the layer we are considering
to XOR together. We can now propagate the mask by applying the following rules.
·
If the mask includes a bit
u
which is output from a XOR gate with inputs
v
and
w
, the mask on the previous layer will include
v
and
w
(see Fig. 4.5).
If the mask includes two bits
u
and
which are output from a duplicate gate
with input
w
, the mask on the previous layer will not include
w
(see Fig. 4.6
with
a
v
b
).
If the mask includes one and only one bit which is output from a duplicate gate
with input
w
, the mask on the previous layer will include
w
(see Fig. 4.6 with
a
=
=
b
).
Computation circuit
Mask circuit
a
⊕
b
X
a
b
(
a
·
Y
)
⊕
(
b
·
Z
) = (
a
⊕
b
)
·
X
Y
Z
X
=
Y
=
Z
Figure 4.6.
Dual circuit of a duplicate gate.
Search WWH ::
Custom Search