Stéphanie Delaune. Easy Intruder Deduction Problems with Homomorphisms. Information Processing Letters, 97(6):213–218, Elsevier Science Publishers, March 2006.
We present complexity results for the verification of security protocols. Since the perfect cryptography assumption is unrealistic for cryptographic primitives with visible algebraic properties, we extend the classical Dolev-Yao model by permitting the intruder to exploit these properties. More precisely, we are interested in theories such as Exclusive or and Abelian groups in combination with the homomorphism axiom. We show that the intruder deduction problem is in PTIME in both cases, improving the EXPTIME complexity results presented in (Lafourcade, Lugiez, Treinen, 2005).
@article{SD-ipl05,
abstract = {We present complexity results for the verification of
security protocols. Since the perfect cryptography
assumption is unrealistic for cryptographic
primitives with visible algebraic properties, we
extend the classical \emph{Dolev-Yao} model by
permitting the intruder to exploit these properties.
More precisely, we are interested in theories such as
\emph{Exclusive or} and \emph{Abelian groups} in
combination with the homomorphism axiom. We show that
the intruder deduction problem is in PTIME in both
cases, improving the EXPTIME complexity results
presented in~(Lafourcade, Lugiez, Treinen,~2005).},
author = {Delaune, St{\'e}phanie},
OPTDOI = {10.1016/j.ipl.2005.11.008},
journal = {Information Processing Letters},
month = mar,
number = {6},
pages = {213-218},
publisher = {Elsevier Science Publishers},
title = {Easy Intruder Deduction Problems with Homomorphisms},
volume = {97},
year = {2006},
nmonth = {3},
lsv-category = {jour},
wwwpublic = {public and ccsb},
}