Cryptography Reference

In-Depth Information

and extensions of this assumption) suces for doing most of crypto-

graphy.)

Our current state of understanding of ecient computation does

not allow us to prove that one-way functions exist. In particular, if

P

then no one-way functions exist. Furthermore, the existence

of one-way functions implies that

=

NP

BPP ⊇ P

(not even “on the average”). Thus, proving that one-way functions

exist is not easier than proving that

NP

is not contained in

; in fact, the former task

seems significantly harder than the latter. Hence, we have no choice (at

this stage of history) but to assume that one-way functions exist. As

justification to this assumption we may only offer the combined beliefs

of hundreds (or thousands) of researchers. Furthermore, these beliefs

concern a simply stated assumption, and their validity follows from

several widely believed conjectures which are central to various fields

(e.g., the conjectured intractability of integer factorization is central to

computational number theory).

Since we need assumptions anyhow, why not just assume what we

want (i.e., the existence of a solution to some natural cryptographic

problem)? Well, first we need to know what we want: as stated above,

we must first clarify what exactly we want; that is, go through the

typically complex definitional stage. But once this stage is completed,

can we just assume that the definition derived can be met? Not really:

once a definition is derived, how can we know that it can be met at

all? The way to demonstrate that a definition is viable (and that the

corresponding intuitive security concern can be satisfied at all) is to

construct a solution based on a
better understood
assumption (i.e.,

one that is more common and widely believed). For example, look-

ing at the definition of zero-knowledge proofs, it is not a-priori clear

that such proofs exist at all (in a non-trivial sense). The non-triviality

of the notion was first demonstrated by presenting a zero-knowledge

proof system for statements, regarding Quadratic Residuosity, which

are believed to be hard to verify (without extra information). Further-

more, contrary to prior beliefs, it was later shown that the existence

of one-way functions implies that any NP-statement can be proved in

zero-knowledge. Thus, facts that were not known to hold at all (and

even believed to be false), were shown to hold by reduction to widely

P

=

NP