Cryptography Reference
In-Depth Information
more efficient implementation of
A
, specifically, one running in time
O
(
n
2
/ε
2
)
·
(
t
G
(
n
)
)).
The modified algorithm
A
is given input
y
+
log(
n
/ε
=
f
(
x
) and a parameter
ε
and
sets
l
1). In the actual description (presented later), it will be
more convenient to use arithmetic of reals instead of Boolean. Hence, we denote
b
(
x
=
log((
n
/ε
2
)
+
1)
b
(
x
,
r
)
and
G
(
y
1)
G
(
y
,
r
)
. The verification of the following
,
r
)
=
(
−
,
r
)
=
(
−
facts is left as an exercise:
Fact 1:
For every
x
, it holds that
E
[
b
(
x
G
(
f
(
x
)
s
(
x
)
,
U
n
)
·
,
U
n
+
e
i
)]
=
·
(
−
1)
x
i
,
where
s
(
x
)
def
2
). (Note that for
x
∈
S
n
,wehave
s
(
x
)
≥
2
ε
.)
Fact 2:
Let
R
be a uniformly chosen
l
-by-
n
Boolean matrix. Then for every
v
=
1
=
2
·
(
s
(
x
)
−
u
∈{
0
,
1
}
l
\{
0
}
l
, it holds that
v
R
and
uR
are pairwise independent and
uniformly distributed in
{
0
,
1
}
n
.
n
and
v
∈{
0
,
1
}
l
, it holds that
b
(
x
,v
R
)
=
b
(
xR
T
Fact 3:
For every
x
∈{
0
,
1
}
,v
).
Using these facts, we obtain the following:
Claim 2.5.4.2:
For any
x
∈
S
n
and a uniformly chosen
l
-by-
n
Boolean matrix
R
,
there exists
σ
∈{
0
,
1
}
l
1
such that, with probability at least
2
, for every 1
≤
i
≤
n
,
the sign of
v
∈{
0
,
1
}
l
b
(
σ,v
)
·
G
(
f
(
x
)
,v
R
+
e
i
) equals the sign of (
−
1)
x
i
.
Proof:
Let
σ
=
xR
T
. Combining the foregoing facts, for every
v
∈{
0
,
1
}
l
\{
0
}
l
,
we have
E
[
b
(
xR
T
,v
)
·
G
(
f
(
x
)
,v
R
+
e
i
)]
=
s
(
x
)
·
(
−
1)
x
i
. Thus, for every such
1
+
s
(
x
)
2
[
b
(
xR
T
G
(
f
(
x
)
v
, it holds that
Pr
,v
)
·
,v
R
+
e
i
)
=
(
−
1)
x
i
]
=
=
s
(
x
).
Using Fact 2,
l
=
log((2
n
/ε
2
)
+
1), and Chebyshev's inequality, the claim
follows.
A last piece of notation:
Let
B
bea2
l
-by-2
l
matrix, with the (
σ,v
) entry being
b
(
σ,v
),
and let
g
i
be a 2
l
-dimensional vector, with the
th entry equal to
G
(
f
(
x
)
e
i
). Thus,
v
,v
R
+
equals
v
∈{
0
,
1
}
l
b
(
th entry in the vector
B g
i
·
G
(
f
(
x
)
,v
R
+
e
i
).
σ
σ,v
the
)
Efficient implementation of algorithm
A
:
On input
y
=
f
(
x
) and a parameter
ε
,
the inverting algorithm
A
sets
l
=
2
)
log((
n
/ε
+
1) and proceeds as follows:
n
, it computes the 2
l
-dimensional vector
g
i
1.
For
i
=
1
,...,
(as defined earlier).
B g
i
.
Let
Z
bea2
l
-by-
n
real matrix in which the
i
th column equals
z
i
.
Let
Z
bea2
l
-by-
n
Boolean matrix representing the signs of the elements in
Z
:
Specifically, the (
i
=
,...,
n
, it computes
z
i
←
2.
For
i
1
j
)th entry of
Z
equals 1 if and only if the (
i
,
,
j
)th entry of
Z
is negative.
3.
Scanning all rows of
Z
, it outputs the first row
z
so that
f
(
z
)
=
y
.
1
By Claim 2.5.4.2, for
x
∈
S
n
, with probability at least
2
, the foregoing algorithm
retrieves
x
from
y
=
f
(
x
). The running time of the algorithm is dominated by
