C.1. Introduction

It is worthwhile to ask the question why public-key cryptography must be based on problems that are only believed to be difficult. Complexity theory suggests concrete examples of provably intractable problems. This appendix provides a brief conceptual explanation why these provably difficult problems cannot be used for building cryptographic protocols. We may consequently conclude that at present we cannot prove a public-key cryptosystem to be secure. That is bad news, but we have to live with it.

Here, we make no attempts to furnish definitions of formal complexity classes. The excellent books by Papadimitriou [229] and by Sipser [280] can be consulted for that purpose. Here is a list of the complexity classes that we require for our discussion. The relationships between these classes are depicted in Figure C.1. All the containments shown in this figure are conjectured to be proper. With an abuse of notations we identify functional problems with decision problems.