  There is a large amount of work dedicated to the formal verification ofsecurity protocols. In this paper, we revisit and extend the NP-completedecision procedure for a bounded number of sessions. We use a, now standard,deducibility constraints formalism for modeling security protocols. Our firstcontribution is to give a simple set of constraint simplification rules, thatallows to reduce any deducibility constraint system to a set of solved forms,representing all solutions (within the bound on sessions).  As a consequence, we prove that deciding the existence of key cycles isNP-complete for a bounded number of sessions. The problem of key-cycles hasbeen put forward by recent works relating computational and symbolic models.The so-called soundness of the symbolic model requires indeed that no key cycle(e.g., enc(k,k)) ever occurs in the execution of the protocol. Otherwise,stronger security assumptions (such as KDM-security) are required.  We show that our decision procedure can also be applied to prove again thedecidability of authentication-like properties and the decidability of asignificant fragment of protocols with timestamps.
We use a, now standard, deducibility constraints formalism for modeling security protocols. Our first contribution is to give a simple set of constraint simplification rules, that allows to reduce any deducibility constraint system to a set of solved forms, representing all solutions (within the bound on sessions).