×

Easy intruder deductions. (English) Zbl 1201.68049

Dershowitz, Nachum (ed.), Verification: Theory and practice. Essays dedicated to Zohar Manna on the occasion of his 64th birthday. Berlin: Springer (ISBN 3-540-21002-4/pbk). Lecture Notes in Computer Science 2772, 225-242 (2003).
Summary: We investigate extensions of the Dolev-Yao model of a passive intruder into a cryptographic protocol by some algebraic properties of cryptographic primitives. We provide sufficient conditions under which the intruder deduction problem is decidable in polynomial time. We apply this result to the equational theory of homomorphism, and show that in this case the intruder deduction problem is linear, provided that the messages are in normal form.
For the entire collection see [Zbl 1045.68009].

MSC:

68P25 Data encryption (aspects in computer science)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI