Cryptography Reference
In-Depth Information
8
Elements of Complexity Theory
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 com-
putational capability. Shannon implicitly explored the frontier based on information
availability. By looking at the foundations of computer sciences, we explore other fron-
tiers in this chapter. We will see that a frontier based on Turing complexity better fits
cryptography.
8.1
Formal Computation
8.1.1
Formal Languages and Regular Expressions
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
,welet
u
||
v
denote the concatenation of
u
and
. 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 a
word which is its number of characters. The length is additive with concatenation (the
length of a concatenated word is the sum of the lengths of concatenatees). A special
word is the null word
v
ε
||
ε
=
ε
||
=
of length zero. We have the property that
u
u
u
for any
word
u
. Concatenation in the set of all words over the alphabet
is thus an associative
law for which
ε
is a neutral element. It is also regular:
u
||
v
=
u
||
w
or
v
||
u
=
w
||
u
implies
v
=
w
for any words
u
,
v
,
w
.
,
five is represented in
unary
by 11111. In many cases, we use the
binary
alphabet
={
Alphabets of cardinality 1 are used in order to represent integers: if
={
1
}
0
,
1
}
.
Search WWH ::
Custom Search