Cryptography Reference
In-Depth Information
Consequently, the notion of expected polynomial-time raises a variety
of conceptual and technical problems. For that reason, whenever possi-
ble, one should prefer the more robust (and restricted) notion of strict
(probabilistic) polynomial-time. Thus, with the
exception of constant-
round
zero-knowledge protocols, whenever we talked of a probabilistic
polynomial-time verifier (resp., simulator) we mean one in the strict
sense. In contrast, with the exception of (8; 12), all results regarding
constant-round
zero-knowledge protocols refer to a strict polynomial-
time verifier and an expected polynomial-time simulator, which is
indeed a small cheat. For further discussion, the reader is referred
to (12).
4.4.3
Related notions: POK, NIZK, and WI
We briefly discuss the notions of proofs of knowledge (POK), non-
interactive zero-knowledge (NIZK), and witness indistinguishable
proofs (WI).
Proofs of Knowledge.
Loosely speaking, proofs of knowledge
(cf. (81)) are interactive proofs in which the prover asserts “knowl-
edge” of some object (e.g., a 3-coloring of a graph), and not merely its
existence (e.g., the existence of a 3-coloring of the graph, which in turn
is equivalent to the assertion that the graph is 3-colorable). Before clar-
ifying what we mean by saying that a machine knows something, we
point out that “proofs of knowledge”, and in particular zero-knowledge
“proofs of knowledge”, have many applications to the design of crypto-
graphic schemes and cryptographic protocols. One famous application
of zero-knowledge proofs of knowledge is to the construction of identi-
fication schemes (e.g., the Fiat-Shamir scheme (58)).
What does it mean to say that a
machine
knows something? Any
standard dictionary suggests several meanings for the verb
to know
,
which are typically phrased with reference to
awareness
,anotionwhich
is certainly inapplicable in the context of machines. We must look for a
behavioristic
interpretation of the verb
to know
. Indeed, it is reasonable
to link knowledge with ability to do something (e.g., the ability to write
down whatever one knows). Hence, we will say that a machine knows
