RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication
Capítulo o parte de un libro (BookPart)
Asymmetric Unification: A New Unification Paradigm for Cryptographic Protocol Analysis
We present a new paradigm for unification arising out of a technique commonly used in cryptographic protocol analysis tools that employ unification modulo equational theories. This paradigm relies on: (i) a decomposition of an equational theory into (R,E) where R is confluent, terminating, and coherent modulo E, and (ii) on reducing unification problems to a set of problems s=?ts=?t under the constraint that t remains R/E-irreducible. We call this method asymmetric unification. We first present a general-purpose generic asymmetric unification algorithm. and then outline an approach for converting special-purpose conventional unification algorithms to asymmetric ones, demonstrating it for exclusive-or with uninterpreted function symbols. We demonstrate how asymmetric unification can improve performanceby running the algorithm on a set of benchmark problems. We also give results on the complexity and decidability of asymmetric unification., S. Escobar and S. Santiago were partially supported by EU (FEDER) and the Spanish MEC/MICINN under grant TIN 2010-21062-C02-02, and by Generalitat Valenciana PROMETEO2011/052. The following authors were partially supported by
NSF: S. Escobar, J. Meseguer, and R. Sasse under CNS 09-04749 and CCF 09-
05584; D. Kapur under CNS 09-05222; C. Lynch, Z. Liu, and C. Meadows under
CNS 09-05378, and P. Narendran and S. Erbatur under CNS 09-05286. Part of the
S. Erbatur’s work was supported while with the Department of Computer Science,
University at Albany, and part of R. Sasse’s work was supported while with the Department of Computer Science, University of Illinois at Urbana-Champaign.