Tree automata with one memory, set constraints and cryptographic protocols

Hubert Comon-Lundh 1 Véronique Cortier 2
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We introduce a class of tree automata that perform tests on a memory that is updated using function symbol application and projection. The language emptiness problem for this class of tree automata is shown to be in DEXPTIME. We also introduce a class of set constraints with equality tests and prove its decidability by completion techniques and a reduction to tree automata with one memory. Finally, we show how to apply these results to cryptographic protocols. We introduce a class of cryptographic protocols and show the decidability of secrecy for an arbitrary number of agents and an arbitrary number of (concurrent or successive) sessions, provided that only a bounded number of new data is generated. The hypothesis on the protocol (a restricted copying ability) is shown to be necessary: without this hypothesis, we prove that secrecy is undecidable, even for protocols without nonces.
Complete list of metadatas

https://hal.inria.fr/inria-00000553
Contributor : Véronique Cortier <>
Submitted on : Wednesday, November 2, 2005 - 2:43:40 PM
Last modification on : Friday, April 12, 2019 - 10:18:03 AM

Identifiers

  • HAL Id : inria-00000553, version 1

Citation

Hubert Comon-Lundh, Véronique Cortier. Tree automata with one memory, set constraints and cryptographic protocols. Theoretical Computer Science, Elsevier, 2005, 331 (1), pp.143-214. ⟨inria-00000553⟩

Share

Metrics

Record views

194