Introduction - Foundations of Cryptography: Basic Tools - page 2

We start by mentioning that much of the content of this topic relies on the assump-
tion that one-way functions exist. The definition of one-way functions captures the sort
of computational difficulty that is inherent to our entire approach to cryptography, an
approach that attempts to capitalize on the computational limitations of any real-life
adversary. Thus, if nothing is difficult, then this approach fails. However, if, as is widely
believed, not only do hard problems exist but also instances of them can be efficiently
generated, then these hard problems can be “put to work.” Thus, “algorithmically bad
news” (by which hard computational problems exist) implies good news for cryptogra-
phy. Chapter 2 is devoted to the definition and manipulation of computational difficulty
in the form of one-way functions.
1.1.1. Encryption Schemes
The problem of providing secret communication over insecure media is the most tra-
ditional and basic problem of cryptography. The setting consists of two parties com-
municating over a channel that possibly may be tapped by an adversary, called the
wire-tapper . The parties wish to exchange information with each other, but keep the
wire-tapper as ignorant as possible regarding the content of this information. Loosely
speaking, an encryption scheme is a protocol allowing these parties to communicate se-
cretly with each other. Typically, the encryption scheme consists of a pair of algorithms.
One algorithm, called encryption , is applied by the sender (i.e., the party sending a mes-
sage), while the other algorithm, called decryption , is applied by the receiver. Hence,
in order to send a message, the sender first applies the encryption algorithm to the
message and sends the result, called the ciphertext , over the channel. Upon receiving a
ciphertext, the other party (i.e., the receiver) applies the decryption algorithm to it and
retrieves the original message (called the plaintext ).
In order for this scheme to provide secret communication, the communicating parties
(at least the receiver) must know something that is not known to the wire-tapper. (Other-
wise, the wire-tapper could decrypt the ciphertext exactly as done by the receiver.) This
extra knowledge may take the form of the decryption algorithm itself or some parameters
and/or auxiliary inputs used by the decryption algorithm. We call this extra knowledge
the decryption key . Note that, without loss of generality, we can assume that the decryp-
tion algorithm is known to the wire-tapper and that the decryption algorithm needs two
inputs: a ciphertext and a decryption key. We stress that the existence of a secret key, not
known to the wire-tapper, is merely a necessary condition for secret communication.
Evaluating the “security” of an encryption scheme is a very tricky business. A
preliminary task is to understand what “security” is (i.e., to properly define what is
meant by this intuitive term). Two approaches to defining security are known. The first
(“classic”) approach is information-theoretic . It is concerned with the “information”
about the plaintext that is “present” in the ciphertext. Loosely speaking, if the ciphertext
contains information about the plaintext, then the encryption scheme is considered
insecure. It has been shown that such a high (i.e., “perfect”) level of security can be
achieved only if the key in use is at least as long as the total length of the messages sent
via the encryption scheme. The fact that the key has to be longer than the information
exchanged using it is indeed a drastic limitation on the applicability of such encryption