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).