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