December 4, 2018
Matteo Campanelli
Modern cryptography is a pessimistic discipline, in at least two ways: pessimistic in its fundamental belief (“There are problems you cannot solve”); pessimistic in its imperative (“Act as if the worst possible thing that can happen will happen”). These two attitudes may be somewhat uncomfortable, but they are clearly useful if they work in building strong security. And indeed they do work and indeed they are useful. Despite their usefulness, though, these two “mantras” have limitations. Take the first one, the “epistemological” pessimism. Given what we know today about complexity theory, there is no (mathematical) proof of its accuracy: all we can do is to assume that that is the case. This implies assuming not only that P != NP but quite some more. How would the world be different if this assumption turned out to be false? And for the second type of pessimism, the “ethical” one: how should we apply it according to the situation? For example, what is the “worst that can happen” in a quantum world (as opposed to one with classical computers)? Finally, can there ever be space for optimism? That is, are there situations where we can reasonably assume that the “worst” is not going to be that bad after all? In my talk I would try and give a broad overview of this topic, to partly (and subjectively) answer the questions above and argue that the two cryptographic “pessimisms” are actually intertwined.