Cryptography Reference
In-Depth Information
modified relation, denoted
R
2
, is defined by
def
={
R
2
((
x
1
,
x
2
)
,w
):
|
x
1
|=|
x
2
|∧∃
i
s.t. (
x
i
,w
)
∈
R
}
(4.5)
Namely,
w
is a witness under
R
2
for the instance (
x
1
,
x
2
) if and only if
w
is a witness
under
R
for either
x
1
or
x
2
.
Proposition 4.6.10:
Let R and R
2
be as before, and let P be a probabilistic
polynomial-time interactive machine that is witness-indistinguishable for R
2
.
Then P is witness-hiding for R
2
under every distribution of pairs of hard instances
induced by an efficient algorithm that randomly selects pairs in R. That is:
Let S be a probabilistic polynomial-time algorithm that on input
1
n
outputs
,w
∈
|
|=
(
x
n and X
n
denotes the distribution induced on the first ele-
ment in the output of S
(1
n
)
. Suppose that
)
R, so that
x
X
n
}
n
∈N
is an ensemble of hard instances
for R. Then P is witness-hiding under the ensemble
{
{
(
X
(1)
n
,
X
(2)
n
)
}
n
∈N
, where X
(1)
n
and X
(2)
n
denote two independent copies of X
n
.
Proof Idea:
Let
S
and
X
n
}
n
∈N
be in the hypothesis. Suppose that some interac-
tive machine
V
∗
finds witnesses, with non-negligible probability (under the fore-
going distribution), after interacting with
P
. By the witness indistinguishability
of
P
it follows that
V
∗
is performing equally well regardless of whether the wit-
ness
{
R
.
Combining the programs
V
∗
and
P
with the algorithm
S
, we derive an algorithm,
denoted
F
∗
, that finds witnesses for
R
(under the distribution
X
n
)
:
On input
x
w
used by
P
on common input (
x
1
,
x
2
) satisfies (
x
1
,w
)
∈
R
or (
x
2
,w
)
∈
L
, algorithm
F
∗
ge
ne
rates at random (
x
,w
)
S
(1
|
x
|
) and sets
x
x
)
∈
=
=
(
x
,
2
, and
x
=
(
x
,
x
) oth
er
wise. Algorithm
F
∗
emulates an inter-
action of
V
∗
with
P
on common input
x
and auxiliary input
w
to
P
, and when
V
∗
outputs a witness
w
, algorithm
F
∗
checks whether or not (
x
,w
)
∈
R
. By the
witness indistinguishability of
P
,
th
e verifier cannot tell the case in which
P
uses
a witness to the first element of
x
from the case in which it uses a witness to
the second. Also, by construction of
F
∗
, if the input to
F
∗
is distributed as
X
n
,
then the proof system is emulated on common input (
X
(1)
n
1
with probability
,
X
(2
n
), where
X
(1)
n
and
X
(2
n
denote two independent copies of
X
n
. Thus, by the foregoing hypothesis,
V
∗
finds a witness for
x
with non-negligible probability (taken over the distribution
of
x
and the random choices of
F
∗
). It follows that
{
X
n
}
n
∈N
is not hard for
R
.
4.6.4. Applications
Applications of the notions presented in this section are scattered in various places in
this topic. In particular, strong witness-indistinguishable proof systems are used in the
construction of constant-round zero-knowledge arguments for
(see Section 4.9.2),
witness-independent proof systems are used in the zero-knowledge proof for Graph
Non-Isomorphism (see Section 4.7.4.3), and witness-hiding proof systems are used for
the efficient identification scheme based on factoring (in Section 4.7.5).
261
NP
