EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Decision and Complexity of Dolev-Yao Hyperproperties

Itsaka Rakotonirina, Gilles Barthe, Clara Schneidewind

Proceedings of the ACM on Programming Languages · 02.01.2024 · 8 (POPL) · 1913-1944

DOI: 10.1145/3632906 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 05.01.2024. Verfasst von Itsaka Rakotonirina und 2 weiteren Autor:innen. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 54 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The formal analysis of cryptographic protocols traditionally focuses on trace and equivalence properties, for which decision procedures in the symbolic (or Dolev-Yao, or DY) model are known. However, many relevant security properties are expressed as DY hyperproperties that involve quantifications over both execution paths and attacker computations (which are constrained by the attacker’s knowledge in the underlying model of computation). DY hyperproperties generalise hyperproperties, for which many decision procedures exist, to the setting of DY models. Unfortunately, the subtle interactions between both forms of quantifications have been an obstacle to lifting decision procedures from hyperproperties to DY hyperproperties. The central contribution of the paper is the first procedure for deciding DY hyperproperties, in the usual setting where the number of protocol sessions is bounded and where the equational theory modelling cryptography is subterm-convergent. We prove that our decision procedure can decide the validity of any hyperproperty in which quantifications over messages are guarded and quantifications over attacker computations are limited to expressing the attacker’s knowledge. We also establish the complexity of the decision problem for several important fragments of the hyperlogic. Further, we illustrate the techniques and scope of our contributions through examples of related hyperproperties.

Zitieren

APA

Rakotonirina, I., Barthe, G., & Schneidewind, C. (2024). Decision and Complexity of Dolev-Yao Hyperproperties. Proceedings of the ACM on Programming Languages, 8(POPL), 1913-1944. https://doi.org/10.1145/3632906

Vancouver

Rakotonirina I, Barthe G, Schneidewind C. Decision and Complexity of Dolev-Yao Hyperproperties. Proceedings of the ACM on Programming Languages. 2024;8(POPL):1913-1944. doi:10.1145/3632906

BibTeX
@article{Rakotonirina2024,
  author = {Rakotonirina, Itsaka and Barthe, Gilles and Schneidewind, Clara},
  title = {Decision and Complexity of Dolev-Yao Hyperproperties},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  volume = {8},
  number = {POPL},
  pages = {1913--1944},
  doi = {10.1145/3632906}
}
Kostenlos starten →