Cryptography Reference
In-Depth Information
is malleable. Then a CCA adversary, when given the challenge ciphertext
c
,
can modify it and obtain a related one, say
c
(note that we are not defining
'related', as we are only trying to give an intuitive idea of the argument). Then the
adversary can query the encryption oracle about
c
(because
c
=
c
) obtaining
the corresponding plaintext
m
. By the malleability property, we assume that
the existing relationship between
c
and
c
corresponds to a known relationship
between the corresponding plaintexts
m
b
and
m
. Then the adversary uses the
knowledge of
m
and this relationship to decide which of
m
0
,
m
1
, is equal to
m
b
.
3.5.4 Concluding Remarks
In this chapter we have seen that complexity and randomness (together with its
computational analogue, pseudo-randomness) are two fundamental concepts that
play a crucial role in relation to encryption schemes, and in fact they are some of
the most important tools underlying modern cryptography. The very definition of
security involves these two concepts when we require that it should be too difficult
for an adversary to break the system with non-negligible probability. Other relevant
points related to randomness are that this concept is essential to generate keys, and
also for encryption algorithms, which should be probabilistic since otherwise an
encryption scheme cannot be CPA secure.
The fact that the precise definitions of security are based on computational
complexity leads to security proofs that, while being only conditional so far are,
nevertheless, very important because they allow the establishment of precise con-
nections between security and the hardness of well-studied computational problems.
To analyze this point of view in more detail, consider the following two quotes by
well-known authors:
.
.. traditionally, all cryptosystems were eventually broken. No guarantee was made as to the
security of the systems, beyond “we tried and could not break it for a while.”
(Goldwasser in [88]),
.
.. there is only
historical
evidence that factorization is an intrinsically hard problem. Gener-
ations of number theorists, a small army of computer scientists, and legions of cryptologists
spent a considerable amount of energy on it, and the best they came up with are relatively
poor algorithms.
(Lenstra and Lenstra in [127]).
There is apparently some tension between these two remarks. Goldwasser empha-
sizes the importance of having a precise definition of security by pointing out the
shortcomings of assuming that a cryptographic scheme is secure because no one
was able to break it so far, yet the Lenstra brothers point out that the factorization
problem, on which the security of the most popular public-key scheme rests, is only
regarded as hard because no one was able to solve it efficiently so far.
However, both remarks are consistent with today's view of security in modern
cryptography. Classical ciphers were all eventually broken and often the break hap-
pened when their security was held in the highest regard. But cryptanalysis was,
