2004 | OriginalPaper | Chapter
Sound Approximations to Diffie-Hellman Using Rewrite Rules
Authors : Christopher Lynch, Catherine Meadows
Published in: Information and Communications Security
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The commutative property of exponentiation that is necessary to model the Diffie-Hellman key exchange can lead to inefficiency when reasoning about protocols that make use of that cryptographic construct. In this paper we discuss the feasibility of approximating the commutative rule for exponentiation with a pair of rewrite rules, for which in unification-based systems, the complexity of the unification algorithm changes from at best exponential to at worst quadratic in the number of variables. We also derive and prove conditions under which the approximate model is sound with respect to the original model. Since the conditions make the protocol easier to reason about and less prone to error, they often turn out to be in line with generally accepted principles for sound protocol design.