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.