Cryptography Reference
In-Depth Information
Chapter 3
Private-Key Encryption
In this chapter we introduce the basic ideas and concepts underlying private-key
encryption (also called symmetric encryption). Particularly important is the concept
of security, which for the classical ciphers studied in Chap.
1
was not precisely
defined.Thus we shall start by looking at the first rigorous definition for this concept,
namely
perfect secrecy
which, while providing the strongest security assurance, has
important practical disadvantages that motivate the introduction of computational
security concepts that aremore suited for practical use. These notions are definedwith
the help of complexity theory and the concept of pseudo-randomness, a weakening of
randomness that takes into account the fact that computational resources are limited.
The security notions also make use of the concepts of one-way function and pseudo-
random generator, which are of crucial importance for cryptography and are also
introduced here.
3.1 Perfect Secrecy
As we have already mentioned, the Vigenère cipher was considered unbreakable
after being in use for several centuries without any weaknesses having been found.
But then Kasiski and Babbage discovered that this cipher was easy to break. This
clearly showed that a long time passing without a cipher being broken was not a good
indicator of security. But a precise definition of security did not come until almost
100 years later, when Shannon formulated it in the context of his ground-breaking
work on information theory [176].
The basic idea that led Shannon to define
perfect secrecy
was that intercepting
a ciphertext should not give the attacker any information about the plaintext nor
any information about future encrypted messages, and that this should happen even
assuming that the adversary has unbounded computational power.
To formalize the concept of perfect security we denote, as before, by
M
,
C
and
K
, the finite sets of plaintexts, ciphertexts and keys corresponding to the encryption
