Information Technology Reference
In-Depth Information
Complexity Problems in the Analysis
of Information Systems Security
A. Slissenko
Laboratory for Algorithmics, Complexity and Logic
University Paris-1, France
slissenko@univ-paris12.fr
Abstract.
The talk is a survey of complexity problems that concern the
analysis of information systems security; the latter means here mainly
proving the requirements properties. Though the complexity aspects of
cryptology is not a topic of the talk, some concepts and questions of this
field will be discussed, as they may be useful for the development security
concepts of general interest. We discuss the decidability and complexity
of the analysis of cryptographic protocols, of the analysis of the problem
of access to information systems and the complexity of detection of some
types of attacks. We argue that many negative results like undecidability
or high lower bounds, though of a theoretical importance, are not quite
relevant to the analysis of practical systems. Some properties of realistic
systems, that could be taken into account in order to try to obtain more
adequate complexity results, will be discussed. Conceptual problems, like
the notion of reducibility that preserves security, will be touched.
1 Relevance of the Complexity Theory
Though security problems related to computers were revealed during early days
of computer science, their variety and diculty were perceived relatively recently
because of their growing pressure on the society. The amount of concrete valu-
able information on security problems is enormous, and a good amount of this
information is available. However, theoretical settings to study the security of
information systems are evidently not yet developed to a satisfactory level. And
taking into account the quantitative and qualitative complexity of the problem,
the way towards a development of productive theories of the security seems to
be not so short.
The goal of this text is to discuss the computational complexity aspects of
the analysis of the information systems security. Why to speak about complex-
ity? The reason is simple: basically, the main security questions that appear in
practice are algorithmic. We wish to verify security properties, we wish to detect
Address:
Dept. of Informatics, University Paris-12, 61 Av. du Gen. de Gaulle, 94010,
Creteil, France.
Member of St Petersburg Institute for Informatics, Russian Academy of Sciences,
St-Petersburg, Russia.
