Computationally Sound Compositional Logic for Security Protocols

Anupam Datta (1) , Ante Derek (1) , John C. Mitchell (1) , Arnab Roy (1) , Vitaly Shmatikov (2) , Mathieu Turuani (3) , Bogdan Warinschi (3)

1 Computer Science Department [Stanford]
2 ECE - Department of Electrical and Computer Engineering - University of Texas
3 CASSIS - Combination of approaches to the security of infinite states systems

We have been developing a cryptographically sound formal logic for proving protocol security properties without explicitly reasoning about probability, asymptotic complexity, or the actions of a malicious attacker. The approach rests on a probabilistic, polynomial-time semantics for a protocol security logic that was originally developed using nondeterministic symbolic semantics. This workshop presentation will discuss ways in which the computational semantics lead to different reasoning methods and report our progress to date in several directions. One significant difference between the symbolic and computational settings results from the computational difference between efficiently recognizing and efficiently producing a value. Among the more recent developments are a compositional method for proving cryptographically sound properties of key exchange protocols, and some work on secrecy properties that illustrates the computational interpretation of inductive properties of protocol roles.

Domaines: Cryptographie et sécurité [cs.CR]

Anupam Datta, Ante Derek, John C. Mitchell, Arnab Roy, Vitaly Shmatikov, et al.. Computationally Sound Compositional Logic for Security Protocols. Workshop on Formal and Computational Cryptography - FCC 2006, Véronique Cortier et Steve Kremer, Jul 2006, Venice/Italy. ⟨inria-00080593⟩