Impossibility Results for Secret Establishment

Date Added: May 2010
Format: PDF

Security protocol design is a creative discipline where the solution space depends on the problem to be solved and the cryptographic operators available. In this paper, the authors examine the general question of when two agents can create a shared secret. Namely, given an equational theory describing the cryptographic operators available, is there a protocol that allows the agents to establish a shared secret? They examine this question in several settings. First, they provide necessary and sufficient conditions for secret establishment using subterm convergent theories. This directly yields a decision procedure for this problem.