<  Back to the Polytechnique Montréal portal

Symbolic approach to the analysis of security protocols

Stéphane Lafrance

Article (2004)

Open Acess document in PolyPublie and at official publisher
Open Access to the full text of this document
Published Version
Terms of Use: All rights reserved
Download (522kB)
Show abstract
Hide abstract


The specification and validation of security protocols often requires viewing function calls - like encryption/decryption and the generation of fake messages explicitly as actions within the process semantics. Following this approach, this paper introduces a symbolic framework based on value-passing processes able to handle symbolic values like fresh nonces, fresh keys, fake addresses and fake messages. The main idea in our approach is to assign to each value-passing process a formula describing the symbolic values conveyed by its semantics. In such symbolic processes, called constrained processes, the formulas are drawn from a logic based on a message algebra equipped with encryption, signature and hashing primitives. The symbolic operational semantics of a constrained process is then established through semantic rules updating formulas by adding restrictions over the symbolic values, as required for the process to evolve. We then prove that the logic required from the semantic rules is decidable. We also define a bisimulation equivalence between constrained processes; this amounts to a generalisation of the standard bisimulation equivalence between (non-symbolic) value-passing processes. Finally, we provide a complete symbolic bisimulation method for constructing the bisimulation between constrained processes.

Uncontrolled Keywords

bisimulation, equivalence-checking, formal methods, noninterference, process algebra, protocols, symbolic

Subjects: 2700 Information technology > 2700 Information technology
2700 Information technology > 2713 Algorithms
Department: Department of Computer Engineering and Software Engineering
PolyPublie URL: https://publications.polymtl.ca/3383/
Journal Title: Journal of Universal Computer Science (vol. 10, no. 9)
Publisher: J.UCS Consortium
DOI: 10.3217/jucs-010-09-1156
Official URL: https://doi.org/10.3217/jucs-010-09-1156
Date Deposited: 17 Jan 2019 15:19
Last Modified: 23 May 2023 12:46
Cite in APA 7: Lafrance, S. (2004). Symbolic approach to the analysis of security protocols. Journal of Universal Computer Science, 10(9), 1156-1198. https://doi.org/10.3217/jucs-010-09-1156


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only

View Item View Item