Skip to Main content Skip to Navigation
Conference papers

The hitchhiker's guide to decidability and complexity of equivalence properties in security protocols

Abstract : Privacy-preserving security properties in cryptographic protocols are typically modelled by observational equivalences in process calculi such as the applied pi-calulus. We survey decidability and complexity results for the automated verification of such equivalences, casting existing results in a common framework which allows for a precise comparison. This unified view, beyond providing a clearer insight on the current state of the art, allowed us to identify some variations in the statements of the decision problems-sometimes resulting in different complexity results. Additionally, we prove a couple of novel or strengthened results.
Document type :
Conference papers
Complete list of metadatas

Cited literature [50 references]  Display  Hide  Download

https://hal.inria.fr/hal-02961617
Contributor : Steve Kremer <>
Submitted on : Thursday, October 8, 2020 - 3:41:09 PM
Last modification on : Wednesday, October 14, 2020 - 4:21:58 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02961617, version 1

Collections

Citation

Vincent Cheval, Steve Kremer, Itsaka Rakotonirina. The hitchhiker's guide to decidability and complexity of equivalence properties in security protocols. Logic, Language, and Security. Essays Dedicated to Andre Scedrov on the Occasion of His 65th Birthday, 2020, Philadelphia, United States. ⟨hal-02961617⟩

Share

Metrics

Record views

14

Files downloads

31