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
Search WWH ::

Custom Search