Cryptography Reference
In-Depth Information
3. The key will usually be a binary string of length
n
. Similarly, the message space
will usually be
}
∗
, i.e., the set of all the finite-length binary strings. As
already mentioned, another possible choice for
M
={
,
0
1
}
(
n
)
for a fixed length
M
is
{
0
,
1
. Although other alphabets can be used, the assumption that the messages are
binary strings is not restrictive in practice since every message can be efficiently
coded in this form.
4. Although not included in the definition, it will usually be the case that
Gen
chooses the key uniformly at random in
(
n
)
n
. As suggested by the previous
discussion, this is very important for the security of the scheme.
{
0
,
1
}
We shall study some important examples of encryption schemes that are currently
used in practice. The classical ciphers we have considered so far may also be regarded
as private-key encryption schemes once a probabilistic key-generation algorithm
Gen
is specified. However, all these schemes—with the exception of the one-time pad and
the pseudo-random one time pad—are highly insecure. Moreover, all of them have
a deterministic encryption algorithm and, as we shall see, probabilistic encryption
is also a crucial requirement for the security of a non-perfectly secret encryption
scheme.
3.5.2 Security Definitions for Private-Key Encryption Schemes
Computational infeasibility, which by algorithmic standards is the enemy of progress, is
actually the cryptographer's best friend.
(Goldwasser, in [89]).
We will now try to make precise the informal notion of computational security
that we have been using in this chapter. Recall that the idea is to base this concept on
the theory of computational complexity and to obtain the notion of computational
security from that of unconditional security by weakening the latter in two ways:
on the one hand, the adversary no longer has unbounded computational power but
is supposed to run in polynomial time instead and, on the other hand, we concede
that the adversary might succeed with negligible probability. Moreover, we will
assume for now that the adversary is an
eavesdropper
who observes the ciphertext
corresponding to a single message and tries to recover it.
In order to arrive at our definition, it is necessary also to define when the adversary
succeeds or, in other words, what it means to “break” the system. It is easy to identify
necessary
conditions for the system to be secure but the most obvious of these
conditions are not usually sufficient. For example, if the adversary is able to recover
the key, then it breaks the system because it is able to decrypt any messages encrypted
with that key, but the converse is not true, i.e., if key recovery is infeasible we cannot
conclude that the system is secure. As another example, it might happen that an
adversary is able to recover the plaintext from the ciphertext without finding the key.
But the infeasibility of plaintext recovery is still insufficient to provide security. It
