Cryptography Reference
In-Depth Information
Alice
consists of her name and the verification key corresponding to her secret signing
key in a predetermined signature scheme. The identification protocol consists of
Alice
signing a random message chosen by the verifier.
A second popular means of identification consists of identifying people by their
ability to answer personal questions correctly. A digital analogue of this common
practice follows. We use pseudorandom functions (see Section 3.6) and zero-knowledge
proofs (of membership in a language). The public record of
Alice
consists of her name
and a “commitment” to a randomly selected pseudorandom function (e.g., either via
a string-commitment to the index of the function or via a pair consisting of a random
domain element and the value of the function at that point). The identification protocol
consists of
Alice
returning the value of the function at a random location chosen by the
verifier and supplying a zero-knowledge proof that the value returned indeed matches
the function appearing in the public record. We remark that the digital implementation
offers more security than the everyday practice. In the everyday setting, the verifier
is given the list of all possible question-and-answer pairs and is trusted not to try to
impersonate the user. Here we have replaced the possession of the correct answers with
a zero-knowledge proof that the answer is correct.
4.7.6. Strong Proofs of Knowledge
Definitions 4.7.2 and 4.7.3 rely in a fundamental way on the notion of
expected
running
time. Specifically, these definitions refer to the
expected
running time of the knowledge
extractor. For reasons discussed in Section 4.3.1.6, we prefer to avoid the notion of
expected
running time whenever possible. Thus, we consider next a more stringent
definition in which the knowledge extractor is required to run in
strict
polynomial time,
rather than in
expected
time inversely proportional to the acceptance probability (as
in Definition 4.7.2). (We also take the opportunity to postulate, in the definition, that
instances not in
L
R
are accepted with negligible probability; this is done by extending
the scope of the validity condition also to
x
's not in
L
R
.)
4.7.6.1. Definition
Definition 4.7.13 (System of Strong Proofs of Knowledge):
Let R be a binary
relation. We say that an interactive function V is a
strong knowledge verifier
for the relation
R if the following two conditions hold:
Non-triviality:
As in Definition 4.7.2.
Strong validity:
There exists a negligible function
1]
andapro-
babilistic
(strict) polynomial-time
oracle machine K such that for every inter-
active function P and every x
µ
:
N →
[0
,
}
∗
, machine K satisfies the following
,
y
,
r
∈{
0
,
1
condition:
Let p
(
x
,
y
,
r
)
and P
x
,
y
,
r
be as in Definition 4.7.2. If p
(
x
,
y
,
r
)
>µ
(
|
x
|
)
, then on
input x and access to oracle P
x
,
y
,
r
, machine K outputs a solution s
∈
R
(
x
)
with
probability at least
1
−
µ
(
|
x
|
)
.
The oracle machine K is called a
strong knowledge extractor
.
