Introduction - Contemporary Cryptography - page 10

In some literature, provable security is mentioned as yet another notion of
security (e.g., [8]). The idea of provable security goes back to the early days of
public key cryptography, when Whitfield Diffie and Martin E. Hellman proposed
a complexity-based proof (for the security of a public key cryptosystem) in their
seminal paper entitled “New Directions in Cryptography” [9]. 4 Theideaisto
show that breaking a cryptosystem is computationally equivalent to solving a hard
problem. This means that one must prove the following two directions:

• If the hard problem can be solved, then the cryptosystem can be broken;

• If the cryptosystem can be broken, then the hard problem can be solved.

Diffie and Hellman proved the first direction for their key exchange protocol
(see Section 16.3). They did not prove the second direction. 5 This is unfortunate,
because the second direction is the important direction from a security perspective.
If we can prove that an adversary who is able to break a cryptosystem is also able
to solve the hard problem, then we can argue that it is very unlikely that such
an adversary really exists and hence that the cryptosystem in question is likely
to be secure. Michael O. Rabin was the first person who found and proposed a
cryptosystem that can be proven to be computationally equivalent to a hard problem
(i.e., the integer factorization problem as captured in Definition 7.11) [11]. The
Rabin public key cryptosystem is further addressed in Section 14.2.2.
The notion of (provable) security has fueled a lot of research since the late
1970s and early 1980s. In fact, there are many (public key) cryptosystems shown
to be provably secure in exactly this sense. It is, however, important to note that a
complexity-based proof is not absolute and that it is only relative to the (assumed)
intractability of the underlying mathematical problem(s). This is a similar situation
to proving that a given problem is NP -complete. It proves that the problem is at least

as difficult as any other -complete problem, but it does not provide an absolute

proof of the computational difficulty of the problem. 6
More recently (i.e., since about the 1990s), people have come up with a
methodology for designing cryptographic systems (typically security protocols) that
are provably secure in the “reductionist” sense mentioned earlier, and that consists
of the following two steps:

NP

4 This paper is the one that officially gave birth to public key cryptography. There is a companion

paper entitled “Multiuser Cryptographic Techniques” that was presented by the same authors at the
National Computer Conference that took place on June 7-10, 1976, in New York City.

5 Ueli M. Maurer made the first serious attempt to prove the second direction [10].

Refer to Section 6.6.2.2 to get a more detailed overview about NP -completeness and NP -complete
problems.

6