TABLE OF CONTENTS Content
? Formal computation: languages, automata, Turing machines
? Ability frontiers: computability, decidability
? Complexity reduction: intractability, NP-completeness, oracles
In Chapter 1 we saw how to formalize secrecy based on information theory with the notion of perfect secrecy. The Shannon Theorem says that secrecy cannot be achieved unless we can afford the technical cost of the Vernam cipher, which is not very practical. The Shannon Theorem was however formulated in the prehistory times of computer science, and the notion of computation complexity did not exist. The security of cryptographic algorithms always relies on a given frontier of computational capability. Shannon implicitly explored the frontier based on information availability. By looking at the foundations of computer sciences, we explore other frontiers in this chapter. We will see that a frontier based on Turing complexity better fits cryptography.
Formally, a language is a set of words. A word is a finite sequence of characters taken from an alphabet. An alphabet is a finite set ?. The basic operation defined on words is concatenation. Given two words u and v, we let u? v denote the concatenation of u and v. We can thus let word denote the word ( w, o, r, d) as the concatenation of four elementary words which consist of single characters. We also define the length of...
