Cryptography Reference

In-Depth Information

that is not known to the wire-tapper. (Otherwise, the wire-tapper can

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 may assume that the decryption algorithm is known

to the wire-tapper, and that the decryption algorithm operates on two

inputs: a ciphertext and a decryption-key. We stress that the existence

of a decryption-key, not known to the wire-tapper, is merely a necessary

condition for secret communication. The above description implicitly

presupposes the existence of an ecient algorithm for generating (ran-

dom) keys.

Evaluating the “security” of an encryption scheme is a very tricky

business. A preliminary task is to understand what is “security” (i.e., to

properly define what is meant by this intuitive term). Two approaches

to defining security are known. The first (“classical”) approach, intro-

duced by Shannon (119), is
information theoretic
. It is concerned with

the “information” about the plaintext that is “present” in the cipher-

text . Loosely speaking, if the ciphertext contains information about

the plaintext then the encryption scheme is considered insecure. It has

been shown that such high (i.e., “perfect”) level of security can be

achieved only if the key in use is at least as long as the
total
amount

of information sent via the encryption scheme (119). This fact (i.e.,

that the key has to be longer than the information exchanged using

it) is indeed a drastic limitation on the applicability of such (perfectly-

secure) encryption schemes.

The second (“modern”) approach, followed in the current text, is

based on
computational complexity
. This approach is based on the the-

sis that it
does not matter
whether the ciphertext contains information

about the plaintext, but rather whether this information can be
e-

ciently extracted
. In other words, instead of asking whether it is
possible

for the wire-tapper to extract specific information, we ask whether it is

feasible
for the wire-tapper to extract this information. It turns out that

the new (i.e., “computational complexity”) approach can offer security

even when the key is much shorter than the total length of the messages

sent via the encryption scheme.