Cryptography Reference
In-Depth Information
with an arbitrary polynomial
q
). We shall use this fact in the proofs of Propositions 4.7.5
and 4.7.6.
4.7.1.4. Discussion
In view of Proposition 4.7.4, we can freely use either of the two formulations of va-
lidity. The formulation of Definition 4.7.2 typically is more convenient when analyz-
ing the effect of a proof of knowledge as a sub-protocol, whereas the formulation of
Definition 4.7.3 typically is more convenient when demonstrating that a given system
is a proof of knowledge. We mention that variants of Proposition 4.7.4 also hold when
R
is not an
NP
-relation (see Exercise 29).
A Reflection.
The notion of a proof of knowledge (and, more so, the notion of a
knowledge extractor used in formalizing it) is related to the simulation paradigm. This
relation is evident in applications in which the knowledge verifier takes some action
A
is such
that it causes no harm to the knowledge verifier if the knowledge prover indeed knows
K
after being convinced that the knowledge prover knows
K
, where action
A
. Following the simulation paradigm, our definition asserts that if action
A
is taken
after the verifier becomes convinced that the prover knows
, then no harm is caused,
since in some sense we can simulate a situation in which the prover actually knows
K
.
Indeed, using the knowledge extractor, we can simulate the prover's view of the entire
interaction (i.e., the proof process and the action taken afterward by the convinced
verifier): In case the prover fails, action
K
is not taken, and so the entire interaction is
easy to simulate. In case the prover succeeds in convincing the verifier, we extract the
relevant knowledge
A
K
A
A
and reach a situation in which action
causes no harm (i.e.,
K
can be simulated based on
).
About Soundness.
In the foregoing definitions, we imposed no requirements regarding
what happens when the knowledge verifier for
R
is invoked on common input not
in
L
R
. The natural requirement is that on input
x
∈
L
R
the verifier will accept with
probability at most
). This holds in many natural cases, but not in the conclusion
of Proposition 4.7.6. See further comments in Sections 4.7.3-4.7.6.
κ
(
|
x
|
An Advanced Comment.
A key feature of both formulations of validity is that they
handle all possible values of
p
(
x
r
) in a “uniform” fashion. This is crucial to most
applications (e.g., see Section 4.7.4) in which a proof of knowledge is used as a sub-
protocol (rather than as the end protocol). Typically, in the former applications (i.e.,
using a proof of knowledge as a sub-protocol), the knowledge error function is required
to be negligible (or even zero). In such cases, we need to deal with all possible values
of
p
(
x
,
y
,
r
) that are not negligible, but we do not know a priori the value of
p
(
x
,
y
,
r
).
We warn that the fact that
p
(
x
,
y
,
r
) is not negligible (as a function of
|
x
|
) does
not
mean that it is noticeable (as a function of
|
x
|
).
19
,
y
,
19
Recall that a function
is
negligible
if for every positive polynomial
p
and all sufficiently large
n
's, it holds that
µ
(
n
)
<
1
/
p
(
n
), whereas a function
ν
:
N → R
is
noticeable
if there exists a polynomial
p
such
that for all sufficiently large
n
's, it holds that
ν
(
n
)
>
1
/
p
(
n
). A function
f
:
N → R
may be neither negligible nor
noticeable: For example, consider the function
f
, defined by
f
(
n
)
def
µ
:
N → R
if
n
is odd, and
f
(
n
)
def
=
2
−
n
=
n
−
2
otherwise.
