Paper Info
Title
On the Relative Soundness of the Free Algebra Model for Public Key Encryption
Abstract
Formal systems for cryptographic protocol analysis typically model cryptosystems in terms of free algebras. Modeling the behavior of a cryptosystem in terms of rewrite rules is more expressive, however, and there are some attacks that can only be discovered when rewrite rules are used. But free algebras are more efficient, and appear to be sound for ''most'' protocols. In [J. Millen, ''On the freedom of decryption'', Information Processing Letters 86 (6) (June 2003) 329-333] Millen formalizes this intuition for shared key cryptography and provides conditions under which it holds; that is, conditions under which security for a free algebra version of the protocol implies security of the version using rewrite rules. Moreover, these conditions fit well with accepted best practice for protocol design. However, he left public key cryptography as an open problem. In this paper, we show how Millen's approach can be extended to public key cryptography, giving conditions under which security for the free algebra model implies security for the rewrite rule model. As in the case for shared key cryptography, our conditions correspond to standard best practice for protocol design.
Year
DOI
Venue
2005
10.1016/j.entcs.2004.05.018
Electr. Notes Theor. Comput. Sci.
Keywords
DocType
Volume
free algebra,free algebra version,model cryptosystems,protocol design,j. millen,public key cryptography,free algebra model,relative soundness,public key encryption,rule model,key cryptography,cryptographic protocol verification,cryptographic protocol analysis,best practice,information processing,cryptographic protocol
Journal
125
Issue
ISSN
Citations 
1
Electronic Notes in Theoretical Computer Science
11
PageRank 
References 
Authors
0.53
11
2
Name
Order
Citations
PageRank
Christopher Lynch1646.86
Catherine Meadows292889.05