Cryptography Reference
In-Depth Information
2
Computational Di
culty and One-way Functions
Modern cryptography is concerned with the construction of systems
that are easy to operate (properly) but hard to foil. Thus, a complexity
gap (between the ease of proper usage and the diculty of deviating
from the prescribed functionality) lies at the heart of modern crypto-
graphy. However, gaps as required for modern cryptography are not
known to exist; they are only widely believed to exist. Indeed, almost
all of modern cryptography rises or falls with the question of whether
one-way functions exist. We mention that the existence of one-way
functions implies that
contains search problems that are hard to
solve
on the average
, which in turn implies that
NP
NP
is not contained
in
BPP
(i.e., a worst-case complexity conjecture).
Loosely speaking, one-way functions are functions that are easy to
evaluate but hard (on the average) to invert. Such functions can be
thought of as an ecient way of generating “puzzles” that are infeasible
to solve (i.e., the puzzle is a random image of the function and a solution
is a corresponding preimage). Furthermore, the person generating the
puzzle knows a solution to it and can eciently verify the validity of
(possibly other) solutions to the puzzle. Thus, one-way functions have,
by definition, a clear cryptographic flavor (i.e., they manifest a gap
between the ease of one task and the diculty of a related one).
