A Formal Semantics for Protocol Narrations

  • Sébastien Briais
  • Uwe Nestmann
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3705)


Protocol narrations are an informal means to describe, in an idealistic manner, the functioning of cryptographic protocols as a single intended sequence of cryptographic message exchanges among the protocol’s participants. Protocol narrations have also been informally “turned into” a number of formal protocol descriptions, e.g., using the spi-calculus. In this paper, we propose a direct formal operational semantics for protocol narrations that fixes a particular and, as we argue, well-motivated interpretation on how the involved protocol participants are supposed to execute. Based on this semantics, we explain and formally justify a natural and precise translation of narrations into spi-calculus.


Operational Semantic Security Protocol Formal Semantic Message Exchange Cryptographic Protocol 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [Aba00]
    Abadi, M.: Security Protocols and their Properties. In: Foundations of Secure Computation, pp. 39–60. NATO ASI. IOS Press, Amsterdam (2000)Google Scholar
  2. [AG99]
    Abadi, M., Gordon, A.D.: A Calculus for Cryptographic Protocols: The Spi Calculus. Information and Computation 148(1), 1–70 (1999)CrossRefzbMATHMathSciNetGoogle Scholar
  3. [BBD+03]
    Bodei, C., Buchholtz, M., Degano, P., Nielson, F., Nielson, H.: Automatic validation of protocol narration. In: Proceedings of 16th IEEE Computer Security Foundations Workshop (CSFW 16), pp. 126–140 (2003)Google Scholar
  4. [BBN04]
    Borgström, J., Briais, S., Nestmann, U.: Symbolic Bisimulation in the Spi Calculus. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 161–176. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  5. [Bla03]
    Blanchet, B.: Automatic Verification of Cryptographic Protocols: A Logic Programming Approach. In: Proceedings of Principles and Practice of Declarative Programming (PPDP 2003). ACM, New York (2003)Google Scholar
  6. [BMV03]
    Basin, D., Mödersheim, S., Viganò, L.: An On-the-Fly Model-Checker for Security Protocol Analysis. In: Snekkenes, E., Gollmann, D. (eds.) ESORICS 2003. LNCS, vol. 2808, pp. 253–270. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  7. [Bri04]
    Briais, S.: Formal proofs about hedges using the Coq proof assistant (2004),
  8. [CJ97]
    Clark, J.A., Jacob, J.L.: A survey of authentication protocol literature. Technical Report 1.0, University of York (1997)Google Scholar
  9. [CM05]
    Cremers, C., Mauw, S.: Operational Semantics of Security Protocols. In: Leue, S., Systä, T.J. (eds.) Scenarios: Models, Transformations and Tools. LNCS, vol. 3466, pp. 66–89. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  10. [DY83]
    Dolev, D., Yao, A.C.: On the security of public key protocols. IEEE Transactions on Information Theory IT-29(12), 198–208 (1983)CrossRefMathSciNetGoogle Scholar
  11. [Gen03]
    Gensoul, C.: Spyer — un compilateur de protocoles cryptographiques. Semester Project Report, EPFL (July 2003)Google Scholar
  12. [JRV00]
    Jacquemard, F., Rusinowitch, M., Vigneron, L.: Compiling and Verifying Security Protocols. In: Parigot, M., Voronkov, A. (eds.) LPAR 2000. LNCS (LNAI), vol. 1955, pp. 131–160. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  13. [Low98]
    Lowe, G.: Casper: A Compiler for the Analysis of Security Protocols. Journal of Computer Security 6, 53–84 (1998)Google Scholar
  14. [Mil]
    Millen, J.K.: CAPSL: Common Authentication Protocol Specification Language,
  15. [MvOV96]
    Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)CrossRefGoogle Scholar
  16. [Pau98]
    Paulson, L.C.: The Inductive Approach to Verifying Cryptographic Protocols. Journal of Computer Security 6(1-2), 85–128 (1998)Google Scholar
  17. [STY05]
    Sumii, E., Tatsuzawa, H., Yonezawa, A.: Translating Security Protocols from Informal Notation into Spi Calculus. IPSJ Transactions on Programming 45 Written in Japanese, abstract in English (2005) (to appear)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Sébastien Briais
    • 1
  • Uwe Nestmann
    • 1
  1. 1.School of Computer and Communication SciencesEPFLSwitzerland

Personalised recommendations