Security protocols, constraint systems, and group theories

Stéphanie Delaune 1, 2 Steve Kremer 3 Daniel Pasaila 4
1 SECSI - Security of information systems
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
3 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 Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : When formally analyzing security protocols it is often im- portant to express properties in terms of an adversary's inability to distinguish two protocols. It has been shown that this problem amounts to deciding the equivalence of two constraint systems, i.e., whether they have the same set of solutions. In this paper we study this equivalence problem when cryptographic primitives are modeled using a group equational theory, a special case of monoidal equational theories. The results strongly rely on the isomorphism between group theories and rings. This allows us to reduce the problem under study to the problem of solving systems of equations over rings. We provide several new decidability and complexity results, notably for equational theories which have applications in security protocols, such as exclusive or and Abelian groups which may additionally admit a unary, homomorphic symbol.
Type de document :
Communication dans un congrès
6th International Joint Conference on Automated Reasoning (IJCAR'12), Jun 2012, Manchester, United Kingdom. Springer, 7364, pp.164-178, 2012, Proceedings of the 6th International Joint Conference on Automated Reasoning (IJCAR'12). 〈10.1007/978-3-642-31365-3_15〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00729091
Contributeur : Steve Kremer <>
Soumis le : jeudi 8 octobre 2015 - 14:47:27
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10
Document(s) archivé(s) le : samedi 9 janvier 2016 - 10:14:26

Fichier

CKP-ijcar12.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Stéphanie Delaune, Steve Kremer, Daniel Pasaila. Security protocols, constraint systems, and group theories. 6th International Joint Conference on Automated Reasoning (IJCAR'12), Jun 2012, Manchester, United Kingdom. Springer, 7364, pp.164-178, 2012, Proceedings of the 6th International Joint Conference on Automated Reasoning (IJCAR'12). 〈10.1007/978-3-642-31365-3_15〉. 〈hal-00729091〉

Partager

Métriques

Consultations de la notice

374

Téléchargements de fichiers

50