Intruders with Caps

Siva Anantharaman; Paliath Narendran; Michael Rusinowitch

hal-00468721, version 1

Intruders with Caps

Siva Anantharaman () ¹, Paliath Narendran () ², Michael Rusinowitch () ³

Rewriting Techniques and Applications - RTA'07 (2007) 20--35

Abstract: In the analysis of cryptographic protocols, a "treacherous" set of terms is one from which an intruder can get access to what was intended to be secret, by adding on to the top of a sequence of elements of this set, a "cap" ormed of symbols legally part of his/her knowledge. In this paper, we give sufficient conditions on the rewrite system modeling the intruder's abilities, such as using encryption and decryption functions, to ensure that it is decidable if such caps exist. The following classes of intruder systems are studied: linear, dwindling, Delta-strong, and optimally reducing; and depending on the class considered, the cap problem (``find a cap for a given set of terms'') is shown respectively to be in P, NP-complete, decidable, and undecidable.

1: Laboratoire d'Informatique Fondamentale d'Orléans (LIFO)
Université d'Orléans : EA4022 – Ecole Nationale Supérieure d'Ingénieurs de Bourges
2: University at Albany
State university of New York
3: CASSIS (INRIA Lorraine - LORIA / LIFC)
INRIA – CNRS : FRE2661 – Université de Franche-Comté – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)

hal-00468721, version 1
http://hal.archives-ouvertes.fr/hal-00468721
oai:hal.archives-ouvertes.fr:hal-00468721
From: Siva Anantharaman <>
Submitted on: Wednesday, 31 March 2010 14:29:10
Updated on: Tuesday, 6 April 2010 11:17:01

See detailed view

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="hal-00468721"><analytic>
<author><persName><forename>Siva</forename><surname>Anantharaman</surname></persName>
<affiliation>
<orgName type="laboratory">LIFO</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<country>FR</country>
<orgName type="institution">Université d'Orléans : EA4022</orgName>
<orgName type="institution">Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
</affiliation>
</author>
<author><persName><forename>Paliath</forename><surname>Narendran</surname></persName>
<affiliation>
<orgName type="team">University at Albany</orgName>
<country>US</country>
<orgName type="institution">State university of New York</orgName>
</affiliation>
</author>
<author><persName><forename>Michael</forename><surname>Rusinowitch</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA / LIFC</orgName>
<orgName type="team">CASSIS</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : FRE2661</orgName>
<orgName type="institution">Université de Franche-Comté</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<title type="main" level="a">Intruders with Caps</title></analytic><monogr><title level="m" type="main">18th International Conference on Term Rewriting and Applications - RTA'07</title><meeting>Rewriting Techniques and Applications - RTA'07</meeting><imprint><publisher>Springer-Verlag</publisher><pubPlace><settlement>Paris</settlement><country>France</country></pubPlace><biblScope type="publicationDate">2007-06-00</biblScope><biblScope type="issue">4533</biblScope><biblScope type="pp">20--35</biblScope></imprint></monogr><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00468721</idno></biblStruct>
</listBibl>
</listBibl>