Cryptography Reference
In-Depth Information
1.
It uniformly and independently selects
s
1
s
l
n
1
l
,...,
∈{
0
,
1
}
and
σ
,...,σ
∈{
0
,
1
}
.
, it computes a string
r
J
←⊕
j
∈
J
s
j
2.
For every non-empty set
J
⊆{
1
,
2
,...,
l
}
and a bit
ρ
J
←⊕
j
∈
J
σ
j
.
3.
For every
i
∈{
1
,...,
n
}
and every non-empty
J
⊆{
1
,...,
l
}
, it computes
z
i
←
ρ
J
r
J
e
i
)
⊕
G
(
y
,
⊕
.
, it sets
z
i
to be the majority of the
z
i
values.
4.
For every
i
∈{
1
,...,
n
}
5.
It outputs
z
=
z
1
···
z
n
.
Remark: An Alternative Implementation.
In an alternative implementation of these
ideas, the inverting algorithm tries all possible values for
σ
l
, computes a string
z
for each of these 2
l
possibilities, and outputs only one of the resulting
z
's, with an ob-
vious preference for a string
z
satisfying
f
(
z
)
=
y
. For later reference, this alternative
algorithm is denoted
A
. (See further discussion in the next subsection.)
Following is a detailed analysis of the success probability of algorithm
A
on inputs
of the form
f
(
x
), for
x
∈
S
n
, where
n
∈
N
. One key observation, which is extensively
used, is that for
x
,α,β
∈{
1
,...,σ
0
,
1
}
n
, it holds that
b
(
x
,α
⊕
β
)
=
b
(
x
,α
)
⊕
b
(
x
,β
)
It follows that
b
(
x
,
r
J
)
=
b
(
x
,
⊕
j
∈
J
s
j
)
=⊕
j
∈
J
b
(
x
,
s
j
). The main part of the analysis is
showing that in case the
σ
j
's are correct (i.e.,
σ
j
=
b
(
x
,
s
j
) for all
j
∈{
1
,...,
l
}
), with
constant probability,
z
i
=
. This is proved by bounding from
below the probability that the majority of the
z
i
's equal
x
i
, where
z
i
=
x
i
for all
i
∈{
1
,...,
n
}
b
(
x
,
r
J
)
⊕
G
(
f
(
x
)
,
r
J
⊕
e
i
) (due to the hypothesis that
σ
j
=
b
(
x
,
s
j
) for all
j
∈{
1
,...,
l
}
).
Claim 2.5.2.2:
For every
x
∈
S
n
and every 1
≤
i
≤
n
,
J
:
b
(
x
1)
x
i
>
1
2
·
1
2
n
Pr
r
J
)
r
J
e
i
)
(2
l
,
⊕
G
(
f
(
x
)
,
⊕
=
−
>
1
−
def
=⊕
j
∈
J
s
j
where
r
J
and the
s
j
's are independently and uniformly chosen in
{
0
,
1
}
n
.
Proof:
For every
J
, define a 0-1 random variable
ζ
J
such that
ζ
J
equals 1 if and
only if
b
(
x
,
r
J
)
⊕
G
(
f
(
x
)
,
r
J
⊕
e
i
)
=
x
i
. Since
b
(
x
,
r
J
)
⊕
b
(
x
,
r
J
⊕
e
i
)
=
x
i
,it
J
r
J
e
i
)
r
J
e
i
).
follows that
ζ
=
1 if and only if
G
(
f
(
x
)
,
⊕
=
b
(
x
,
⊕
The reader can easily verify that each
r
J
n
, and
is uniformly distributed in
{
0
,
1
}
the same holds for each
r
J
e
i
. It follows that each
J
⊕
ζ
equals 1 with probability
J
's are pairwise
independent by showing that the
r
J
's are pairwise independent. For every
J
=
K
,
without loss of generality, there exist
j
∈
J
and
k
∈
K
−
J
. Hence, for every
α,β
∈{
1
1
s
(
x
), which by
x
∈
S
n
is at least
2
+
2
p
(
n
)
. We show that the
ζ
0
,
1
}
n
,wehave
Pr
[
r
K
=
β
|
r
J
=
α
]
=
Pr
[
s
k
=
β
|
s
j
=
α
]
[
s
k
=
Pr
=
β
]
[
r
K
=
Pr
=
β
]
