Observational equivalence and security games: Enhancing the formal analysis of security protocols

The formal analysis of security protocols uses abstract language to describe the security protocols, and current protocol descriptions sometimes overlook the security aspects related to cryptographic primitives. In this study, we integrate the security notions of cryptographic primitives with formal methods. Particularly, we use observational equivalence to create security games within the symbolic model. This innovative approach allows for the automation of security detection for cryptographic primitives within the symbolic model. In addition, we have designed and implemented various cryptographic primitives that satisfy different security properties and detect them with our developed security games. The results confirm the effectiveness of our security games. It is worth mentioning that the cryptographic primitives and the characterization of adversary capabilities discussed in this paper can be extended to the formal analysis of other protocols. The ultimate goal is to relax the assumption of perfect encryption and narrow the gap between the formal analysis of security protocols and the real world.