@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}, pdf = {papers/2010/0_CSF2010.pdf}, 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, user = {benschmi} }