On the Use of Complexity in Cryptography Acomputational complexity gap, captured in the defi- nition of one-way functions, is a necessary and sufficient condition for much of modern cryptography. Loosely speaking, one-way functions are functions that are easy to compute but hard to invert (in an average-case sense). The existence of one-way functions implies that P is different from NP, which means that such a complexity gap is only widely conjectured to exist (rather than known for a fact). We demonstrate the use of this gap in the case of the archetypical cryptographic task of providing secret communication, which in turn is reduced to the construction of encryption schemes.

In the second case, known as the public-key case, the receiver invokes the key-generation process, publicizes the encryption key e (but not the decryption key d), and the sender uses e to generate encryptions as before. This allows everybody (not only parties that the receiver trusts) to send encrypted messages to the receiver; however, in such a case the adversary also knows the encryption key e. Thus, the information available to the adversary in this case is a sequence of encrypted messages, sent over the channel, using a fixed encryption key that is also known. In both cases, security amounts to asserting that it is infeasible for the adversary to learn anything from the information available to it. That is, whatever the adversary can efficiently compute from the public information can be efficiently computed from scratch.

Note that in the private-
key case, we may assume,
without loss of generality,
that e = d; whereas in the
public-key case, d must
be hard to compute from
e. Private-key encryption
schemes exist if and only
if one-way functions exist.
Public-key encryption
schemes can be constructed
based on a seemingly
stronger assumption, yet
this assumption is implied by
widely believed conjectures
such as the conjectured
intractability of factoring
integers.

BEYOND ENCRYPTION
SCHEMES
Cryptography encompasses
much more than methods
for providing secret
communication. Another
basic cryptographic
task is that of providing
authenticated
communication, which
in turn is reduced to
the construction of
signature (and/or message
authentication) schemes.
In general, cryptography
is concerned with the
construction of schemes
that maintain any desired
functionality under malicious
attempts aimed at making
these schemes deviate from
their prescribed functionality.
A secure implementation of
a multi-party functionality
is a multi-party protocol in
which the impact of malicious
parties is effectively
restricted to application of
the prescribed functionality
to inputs chosen by the
corresponding parties. One
major result in this area
states that, under plausible
assumptions regarding
computational difficulty,
any efficiently computed
functionality can be securely
implemented.