Cryptography Reference
In-Depth Information
The Naive View
The Actual Proof
R
Good
Rows
S
C
Good Columns
Figure 2.2:
The naive view versus the actual proof of Proposition 2.3.3.
def
=
1
2
n
.
Assume for simplicity that
A
is deterministic. Consider an
N
-by-
N
matrix with
entries corresponding to pairs (
x
1
,
−
0
.
55
=
0
.
45, for infinitely many
n
's. Consider any such
n
, and let
N
x
2
)
∈{
0
,
1
}
n
×{
0
,
1
}
n
such that entry (
x
1
,
x
2
)
is marked 1 if
A
successfully inverts
g
on input
g
(
x
1
,
f
(
x
2
)) and
is marked zero otherwise. Our contradiction hypothesis is that the fraction of
1-entries in the matrix is greater than 45%.
The naive (unjustified) assumption is that
A
operates separately on each el-
ement of the pair (
f
(
x
1
)
x
2
)
=
(
f
(
x
1
)
,
f
(
x
2
)). If that were the case, then the success region
of
A
would have been a generalized rectangle
R
,
n
n
×
C
⊆{
0
,
1
}
×{
0
,
1
}
(i.e.,
corresponding to all pairs (
x
1
,
x
2
) such that
x
1
∈
R
and
x
2
∈
C
for some sets
n
and
C
⊆{
0
,
1
}
n
). Using the hypothesis that
f
is
1
R
⊆{
0
,
1
}
3
-one-way, we have
3
·
N
, and so
|
R
×
C
|
2
4
|
R
|
,
|
C
|≤
≤
9
<
0
.
45, in contradiction to our hypothesis
N
2
regarding
A
.
However, as stated earlier, the naive assumption cannot be justified, and so a
more complex argument is required. In general, the success region of
A
, denoted
S
, may be an arbitrary subset of
{
0
,
1
}
n
satisfying
|
S
|
>
0
.
45
·
N
2
(by
the contradiction hypothesis). Let us call a row
x
1
(resp., column
x
2
)
good
if it
contains at least 0.1% of 1-entries; otherwise it is called
bad
. (See Figure 2.2.)
The main algorithmic part of the proof is establishing the following claim.
n
×{
0
,
1
}
Claim 2.3.3.1:
The fraction of good rows (resp., columns) is at most
66.8%.
Once this claim is proved, all that is left is straightforward combinatorics (i.e.,
counting). That is, we upper-bound the size of
S
by counting separately the number
of 1-entries in the intersection of good rows and good columns and the 1-entries
in bad rows and bad columns: By Claim 2.3.3.1, there are at most (0
668
N
)
2
entries in the intersection of good rows and good columns, and by definition
the number of 1-entries in each bad row (resp., bad column) is at most 0
.
.
001
N
.
668
N
)
2
N
2
, in contradiction to our
Thus,
|
S
|≤
(0
.
+
2
·
N
·
0
.
001
N
<
0
.
449
·
hypothesis (i.e.,
|
S
|
>
0
.
45
·
N
2
).
