TR05-02 (2005) – Decidability and Complexity Results for Security Protocols

F. L. Tiplea, C. Enea, C. V. Birjoveanu

Security protocols are prescribed sequences of interactions between entitiesdesigned to provide various security services across distributed systems. Securityprotocols are often wrong due to the extremely subtle properties they are supposedto ensure. Deciding whether or not a security protocol assures secrecy is one ofthe main challenge in this area.In this paper we survey the most important decidability and complexity resultsregarding the secrecy problem for various classes of security protocols, such asbounded protocols, finite-sessions protocols, normal protocols, and tagged protocols.All the results are developed under the same formalism. Several flawed statementsclaimed in the literature are corrected. Simplified proofs and reductions, aswell as slight extensions of some known results, are also provided.

Bibtex

@TechReport{dcrsp,
author = "Ferucio L. {c T}iplea and C. Enea and C. V. B{^ i}rjoveanu}",
title = "Decidability and Complexity Results for Security
                          Protocols",
institution = "``Al.I.Cuza'' University of Ia{c s}i, 
                 Faculty of Computer Science",
year = "2005",
number = "TR 05-02",
note = "URL:http://www.infoiasi.ro/~tr/tr.pl.cgi"
}