@InProceedings{ schmidt.ea:impossibility:2010,
abstract = {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, we
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?We examine this question in several settings. First,
we provide necessary and sufficient conditions for secret
establishment using subterm convergent theories. This
directly yields a decision procedure for this problem. As a
consequence, we obtain impossibility results for symmetric
encryption and signature schemes. Second, we use algebraic
methods to prove impossibility results for two important
theories that are not subterm convergent: XOR and abelian
groups. Finally, we develop a general combination result
that enables modular impossibility proofs. For example, the
results for symmetric encryption and XOR can be combined to
obtain impossibility for the joint theory. },
author = {Benedikt Schmidt and Patrick Schaller and David Basin},
booktitle = {23nd IEEE Computer Security Foundations Symposium (CSF
2010)},
language = {USenglish},
month = 7,
organization = {IEEE Computer Society Washington, DC, USA},
pages = {261--273},
publisher = {IEEE Computer Society},
title = {Impossibility Results for Secret Establishment},
url = {http://www.computer.org/portal/web/csdl/doi/10.1109/CSF.2010.25},
year = 2010
}