Cryptography Reference
In-Depth Information
)
def
where
(
I
,π
=
P
(
x
,
R
)
,
R
is a random variable uniformly distributed in
poly(
|
x
|
)
, and R
I
is the sub-string of R at positions I
{
0
,
1
}
⊆{
1
,
2
,...,
poly(
|
x
|
)
}
.
That is, R
I
=
r
i
1
···
=
r
1
···
=
(
i
1
,...,
r
i
t
, where R
r
t
and I
i
t
)
.
Soundness:
For every x
∈
L and every algorithm B,
1
3
Pr
[
V
(
x
,
R
I
,
I
,π
)
=
1]
≤
)
def
where
(
I
,π
=
B
(
x
,
R
)
,
R
is
a
random
variable
uniformly
distributed
in
poly(
|
x
|
)
, and R
I
is the sub-string of R at positions I
{
0
,
1
}
⊆{
1
,
2
,...,
poly(
|
x
|
)
}
.
In both cases, I is called the set of
revealed bits
and
π
is called the
certificate
.
Zero-knowledge is defined as before, with the exception that we need to simulate
(
x
,
R
I
,
P
(
x
,
R
))
=
(
x
,
R
I
,
I
,π
)
rather than
(
x
,
R
,
P
(
x
,
R
))
.
As stated earlier, we do not suggest the hidden-bits model as a realistic model. The
importance of the model stems from two facts. First, it is a “clean” model that fa-
cilitates the design of proof systems (in it); second, proof systems in the hidden-bits
model can be easily transformed into non-interactive proof systems (i.e., the realistic
model). The transformation (which utilizes a one-way permutation
f
with hard-core
b
)
follows.
Construction 4.10.4 (From Hidden-Bits Proof Systems to Non-Interactive
Ones):
Let
(
P
V
)
be a hidden-bits proof system for L, and suppose that f
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
and b
:
{
0
,
1
}
∗
→{
0
,
1
}
are polynomial-time-computable. Fur-
thermore, let m
,
poly(
n
)
denote the length of the common reference string for
common inputs of length n, and suppose that f is
1-1
and length-preserving.
Following is a specification of a non-interactive system
(
P
,
=
V
)
:
n
.
Common input:
x
∈{
0
,
1
}
n
.
Common reference string:
s
=
(
s
1
,...,
s
m
)
, where each s
i
is in
{
0
,
1
}
Prover (denoted
P
):
1.
computes r
i
=
b
(
f
−
1
(
s
i
))
for i
=
1
,
2
,...,
m,
2.
invokes P to obtain
(
I
,π
)
=
P
(
x
,
r
1
···
r
m
)
,
def
=
(
f
−
1
(
s
i
1
)
f
−
1
(
s
i
t
))
for I
3.
outputs
(
I
,π,
p
I
)
, where p
I
···
=
(
i
1
,...,
i
t
)
.
Verifier (denoted
V
)
: Given the prover's output
(
I
,π,
(
p
1
···
p
t
))
, the verifier
1.
checks that s
i
j
=
f
(
p
j
)
for each i
j
∈
I (in case a mismatch is found, V
halts
and rejects
),
2.
computes r
i
=
b
(
p
i
)
, for i
=
1
,...,
t , lets r
=
r
1
,...,
r
t
,
3.
invokes V on
(
x
,
r
,
I
,π
)
and accepts if and only if V accepts.
Proposition 4.10.5:
Let
(
P
,
V
)
,L, f,b,and
(
P
,
V
)
be as in Construction 4.10.4.
Then
(
P
,
V
)
is a non-interactive proof system for L, provided that
Pr
[
b
(
U
n
)
=
1
1]
2
. Furthermore, if P is zero-knowledge and b is a hard-core of f , then P
is zero-knowledge too.
=
