Skeletons, Homomorphisms, and Shapes: Characterizing Protocol Executions 1

In this paper we develop a framework, based on strand spaces, for reasoning about cryptographic protocols and characterizing their executions. We define skeletons, homomorphisms, and shapes. Skeletons model partial information about regular (honest) behavior in an execution of a cryptographic protocol. A homomorphism between skeletons is an information-preserving map. Much protocol analysis may be regarded as an exploration of the properties of the category of skeletons and homomorphisms. A set of skeletons can characterize all runs of the protocol; the smallest such set is the set of shapes. This approach is a foundation for mechanizing protocol analysis.