Cryptography Reference
In-Depth Information
4.7.1.3. Knowledge Verifiers
Now that all the machinery is ready, we present the definition of a system for proofs of
knowledge. Actually, the definition is a generalization (to be motivated by the subse-
quent applications) in which we allow an error parameter specified by the function
κ
.
At first reading, one can set the function
κ
to be identically zero.
Definition 4.7.2 (System for Proofs of Knowledge):
Let R be a binary relation
and
1]
. We say that an interactive function V is a
knowledge verifier
for the relation
R with
knowledge error
κ
if the following two conditions hold:
κ
:
N →
[0
,
Non-triviality:
There exists an interactive machine P such that for every
(
x
R
all possible interactions of V with P on common input x and auxiliary input y are
accepting.
,
y
)
∈
κ
·
Validity (with error
)
and a probabilistic oracle
machine K such that for every interactive function P, every x
):
There exists a polynomial q
(
∈
L
R
, and every
}
∗
, machine K satisfies the following condition:
y
,
r
∈{
0
,
1
Denote by p
(
x
,
y
,
r
)
the probability that the interactive machine V ac-
cepts, on input x , when interacting with the prover specified by P
x
,
y
,
r
.If
p
(
x
,
y
,
r
)
>κ
(
|
x
|
)
, then, on input x and with access to oracle P
x
,
y
,
r
, ma-
chine K outputs a solution s
∈
R
(
x
)
within an expected number of steps
bounded by
)
p
(
x
,
y
,
r
)
−
κ
(
|
x
|
)
The oracle machine K is called a
universal knowledge extractor
.
q
(
|
x
|
When
)
is identically zero, we simply say that V is a
knowledge verifier for the
relation
R. An interactive pair
(
P
κ
(
·
V
)
such that V is a knowledge verifier for a
relation R and P is a machine satisfying the non-triviality condition (with respect
to V and R) is called a
system for proofs of knowledge for the relation
R.
,
An alternative formulation of the validity condition follows. It postulates the existence of
a probabilistic oracle machine
K
(as before). However, instead of requiring
K
P
x
,
y
,
r
(
x
)to
always
output a solution within an expected time inversely proportional to
p
(
x
,
y
,
r
)
−
κ
(
|
x
|
), the alternative requires
K
P
x
,
y
,
r
(
x
) to run in expected
polynomial time
and output
a solution with probability at least
p
(
x
,
y
,
r
)
−
κ
(
|
x
|
). In fact, we can further relax the
alternative formulation by requiring that a solution be output with probability at least
(
p
(
x
,
y
,
r
)
−
κ
|
x
|
/
|
x
|
(
))
poly(
).
Definition 4.7.3 (Validity with Error
κ
, Alternative Formulation):
Let V ,
r
)
be as in Definition 4.7.2. We say that V
satisfies the alternative validity condition with error
P
x
,
y
,
r
(with x
∈
L
R
), and p
(
x
,
y
,
if there exists a prob-
abilistic oracle machine K and a positive polynomial q such that on input x
and with access to oracle P
x
,
y
,
r
, machine K runs in expected polynomial time
and outputs a solution s
κ
∈
R
(
x
)
with probability at least
(
p
(
x
,
y
,
r
)
−
κ
(
|
x
|
))
/
q
(
|
x
|
)
.
