Cryptography Reference
In-Depth Information
Chapter 8
Public-Key Encryption
The preceding chapter offered a brief glimpse at the birth of public-key cryptography
and some of its basic features. In the present chapter we continue the study of public-
key cryptography by discussing one of its main themes: public-key encryption.
8.1 Public-Key Encryption Schemes
of enabling secure communication between two parties that do not have to share
a common secret key. That this should be possible was the revolutionary idea of
Diffie and Hellman, who realized the possibility of designing an encryption scheme
in which it is computationally infeasible to find the decryption algorithm from the
encryption one. This, in turn, entails that the same key cannot be used for both
encryption and decryption as happens in private-key cryptography and, as explained
encryption and a private key
sk
which is used for decryption.
This idea was suggested by the fact that in the real world there are actions that are
easily performed but not easily reversed. A simple example is provided by a padlock
that can easily be locked without a key but is very difficult to unlock. A telephone
book provides a less physical analogy. Using it, it is easy to check the telephone
number corresponding to a user of the system but it is much more difficult to find
the name of the user with a given number. In the first case, one only has to go through
the letters in the name using the fact that names are alphabetically ordered. Thus if the
book has
n
telephone numbers and the names are constructed without redundancy
from an alphabet with
b
symbols, then strings of log
b
n
symbols are sufficient to
write down all the names and so to locate a name in the topic one only needs to go
through at most log
b
n
symbols. On the other hand, since the telephone numbers are
not sorted, for the reverse process one has to go through
n
/
2 numbers on average
