Information Technology Reference
In-Depth Information
undecidable whether the virus will be launched or not. But it is clear that if
we know what is our initial program about and what is its structure we can
find even by a static analysis a presence of a suspicious part in it. And this is
sucient for the detection of a possible insecurity.
Taken theoretically, the domain of security is not yet suciently well de-
fined. And algorithmic facets cannot cover many aspects involved in practical
security — they are very different: human, social, juridical, related to hardware
emissions, related to hardware or software functionality — just to mention those
usually addressed in the courses on security (there are many topics that give a
general coverage of security problems and activities to ensure security making
accent on administration, not on technical issues, e. g. [4,16]; B. Schneier [23]
presents the security problem in a fascinating style clearly explaining that it is
far from being a technical problem).
The complexity theory may help to understand better algorithmic questions,
and if to think about Kolmogorov complexity, some information theoretic issues.
We will discuss only questions where computational complexity seems to be
relevant. The choice of topics to discuss is very subjective, not to speak about
references that are rather random.
2 The Problem of Access
The access can be protected by some piece of secrete information (password,
encryption/decryption key, place where information is hidden), by a policy mon-
itoring the access or otherwise
3
. The security problems that arise concern the
complexity of the mechanism of protection itself, the complexity of breaching it
and the complexity of verification either of its properties or of properties of its
applications.
For example, for a public key encryption/decryption method based on num-
ber theory (RSA, El Gamal) the speed of applying the mechanism is essential,
and it is a lower level complexity problem, the complexity of breaching the en-
cryption is a higher level complexity problem, and the verification of security
properties a cryptographic protocol that uses this kind of encryption, is one
more type of problems related to complexity. The complexity study of this set of
problems is the most advanced one, as well as the conceptual framework. Cryp-
tography itself is not our subject, and not the dominating subject of the mass
concerns about information systems security nowadays. However, the theoretical
frameworks developed in cryptography are of great value for study many other
security problems. We will discuss it below.
What is slightly astonishing, is that steganography and watermarking, that
seem to have a theoretical flavor similar to that of cryptography, are not su-
ciently intensively studied from the complexity and information theoretic view-
points. Sure, there are many particular features of these domains that differ
them from cryptography. Particular pattern learning and the respective pattern
3
I discuss examples, but not exhaustive listing. I have no intention to give any clas-
sification or ontology.
