Cryptography Reference
In-Depth Information
before the second half of the twentieth century, an obscure art practised by very
few people who used only their ingenuity to develop themselves the “ad-hoc” meth-
ods they used. In contrast, cryptography—or cryptology, since cryptanalysis is an
indispensable complement—is now largely a science and, when a problem of cryp-
tologic relevance such as, for example, the integer factorization problem, is consid-
ered hard, it is because the scientific community (formed by mathematicians and
computer scientists in this case) supports this idea. Therefore, having the security
of a system precisely defined and related to a specific and well-understood prob-
lem is a big advantage. For example, we will see in Chap.
7
that the security of
RSA may be related to the factorization problem and, even if we have not proved
that factoring is hard and, moreover, the presumed hardness of factoring is not
known to be sufficient for the security of RSA, the situation is much more satis-
factory than if this relation were not known and we worked only with the RSA
function.
In this chapter we have already discussed a reduction of this type, namely the
two-step reduction that shows that the BBS-based pseudo-random one-time pad
is IND-EAV secure under the factoring assumption. First, the problem is reduced
to showing that BBS is a PRG (in the strong cryptographic sense), and then the
latter problem is reduced to the factoring assumption. The reduction is tighter
than in the case of RSA mentioned above, because now the factoring assump-
tion is not just necessary but also sufficient for the IND-EAV security of the
scheme. Although we do not have a guarantee that the factorization problem is
hard, we are on firmer ground that if we only worked under the generic assump-
tion that a pseudo-random generator exists. In Chap.
8
we show that CCA secu-
rity (which is much stronger than IND-EAV security) can also be attained for a
public-key encryption scheme assuming the hardness of a well-known computational
problem.
Summing up these remarks, the security reductions that show that a scheme sat-
isfies a precise security definition if some computational problem is hard, are—
despite some limitations discussed, for example, in [120]—useful because they
place the question of the security of a system on a better foundation. It would be
nice to have proofs of security not relying on unproven assumptions but this is a
very difficult task due to the inherent difficulty of proving lower bounds for the
computational complexity of a problem. This leads to the somewhat paradoxical
situation that, while there are encryption schemes that are proven to be secure in
the strongest sense (the one-time pad has perfect secrecy), the existence of non-
unconditionally secure encryption schemes that are secure in the weaker sense, i.e.,
computationally secure, has not been proved so far. Finally, we remark that in this
chapter we have only given a short introduction to the most important concepts
that serve to establish the foundations of cryptography and we have not given full
proofs of several of the results mentioned. For the reader interested in the theo-
retical foundations of cryptography, an excellent introduction is [109], while [86,
87] are more advanced references that go deep on all the subjects discussed in this
chapter.
