Skip to Main content Skip to Navigation
Journal articles

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
Contributor : Véronique Cortier <>
Submitted on : Wednesday, November 2, 2005 - 2:43:40 PM
Last modification on : Thursday, July 2, 2020 - 5:26:02 PM


  • HAL Id : inria-00000553, version 1


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⟩



Record views