Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Static Equivalence is Harder than Knowledge
EPFL.
2006 (English)In: Electronical Notes in Theoretical Computer Science, ISSN 1571-0661, E-ISSN 1571-0661, Vol. 154, no 3, 45-57 p.Article in journal (Refereed) Published
Abstract [en]

There are two main ways of defining secrecy of cryptographic protocols. The first version checks if the adversary can learn the value of a secret parameter. In the second version, one checks if the adversary can notice any difference between protocol runs with different values of the secret parameter.

We give a new proof that when considering more complex equational theories than partially invertible functions, these two kinds of secrecy are not equally difficult to verify. More precisely, we identify a message language equipped with a convergent rewrite system such that after a completed protocol run, the first problem mentioned above (adversary knowledge) is decidable but the second problem (static equivalence) is not. The proof is by reduction of the ambiguity problem for context-free grammars. 

Place, publisher, year, edition, pages
2006. Vol. 154, no 3, 45-57 p.
Keyword [en]
Security protocol analysis, Term rewriting, Decidability
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-161487DOI: 10.1016/j.entcs.2006.05.006OAI: oai:DiVA.org:uu-161487DiVA: diva2:456287
Conference
EXPRESS'05 12th International Workshop on Expressiveness in Concurrency 27 August, 2005 San Francisco, USA
Note
Conference paper presented at the EXPRESS'05 12th International Workshop on Expressiveness in Concurrency 27 August, 2005 San Francisco, USAAvailable from: 2011-12-06 Created: 2011-11-14 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

fulltext(441 kB)120 downloads
File information
File name FULLTEXT03.pdfFile size 441 kBChecksum SHA-512
3c119f7179aa38172858029d69e3b3e5f337ecdee0ea892d62864f905d979768dc6abd989c66726cb54c546a96fe016ee3a857c77cb5e24957f91f5b30d74092
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Borgström, Johannes
In the same journal
Electronical Notes in Theoretical Computer Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 120 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 425 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf