Cryptography Reference
In-Depth Information
plaintext
plaintext
ciphertext
E
D
X
X
e
e
e
d
Sender's protected region
Receiver's protected region
ADVERSARY
The key-pair
(
e, d
)
is generated by the receiver, who posts the
encryption-key
e
on a public media, while keeping the decryption-
key
d
secret.
Fig. 5.1 Public-key encryption schemes - an illustration.
The computational complexity approach enables the introduction of
concepts and primitives that cannot exist under the information theo-
retic approach. A typical example is the concept of
public-key encryp-
tion schemes
, introduced by Die and Hellman (49). Recall that in the
above discussion we concentrated on the decryption algorithm and its
key. It can be shown that the encryption algorithm must get, in addition
to the message, an auxiliary input that depends on the decryption-key.
This auxiliary input is called the
encryption-key
. Traditional encryp-
tion schemes, and in particular all the encryption schemes used in the
millennia until the 1980s, operate with an encryption-key that equals
the decryption-key. Hence, the wire-tapper in these schemes must be
ignorant of the encryption-key, and consequently the
key distribution
problem arises; that is, how can two parties wishing to communicate
over an insecure channel agree on a secret encryption/decryption key.
(The traditional solution is to exchange the key through an alterna-
tive channel that is secure though (much) more expensive to use.)
The computational complexity approach allows the introduction of
encryption schemes in which the encryption-key may be given to the
wire-tapper without compromising the security of the scheme. Clearly,
the decryption-key in such schemes is different from the encryption-
