Safely Composing Security Protocols ⋆

Abstract. Security protocols are small programs that are executed in hostile environments. Many results and tools have been developed to formally analyze the security of a protocol. However even when a protocol has been proved secure, there is absolutely no guarantee if the protocol is executed in an environment where other protocols, possibly sharing some common identities and keys like public keys or long-term symmetric keys, are executed. In this paper, we show that whenever a protocol is secure, it remains secure even in an environment where arbitrary protocols are executed, provided each encryption contains some tag identifying each protocol, like e.g. the name of the protocol.