Security protocols are prescribed sequences of interactions between entities designed to provide various security services across distributed systems. Security protocols are often wrong due to the extremely subtle properties they are supposed to ensure. Deciding whether or not a security protocol assures secrecy is one of the main challenge in this area.
In this paper we survey the most important decidability and complexity results regarding the secrecy problem for various classes of security protocols, such as bounded protocols, finite-sessions protocols, normal protocols, and tagged protocols. All the results are developed under the same formalism. Several flawed statements claimed in the literature are corrected. Simplified proofs and reductions, as well as slight extensions of some known results, are also provided.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com