Paper 2012/242

Less is More: Relaxed yet Composable Security Notions for Key Exchange

C. Brzuska, M. Fischlin, N. P. Smart, B. Warinschi, and S. Williams


Although they do not suffer from clear attacks, various key agreement protocols (for example that used within the TLS protocol) are deemed as insecure by existing security models for key exchange. The reason is that the derived keys are used within the key exchange step, violating the common key indistinguishability requirement. In this paper we propose a new security definition for key exchange protocols that offers two important benefits. Our notion is weaker than the more established ones and thus allows the analysis of a larger class of protocols. Furthermore, security in the sense that we define enjoys rather general composability properties. In addition our composability properties are derived within game based formalisms, and do not appeal to any simulation based paradigm. Specifically, for protocols whose security relies exclusively on some underlying symmetric primitive we show that they can be securely composed with key exchange protocols provided that two main requirements hold: 1) no adversary can break the underlying {\em primitive}, even when the primitive uses keys obtained from executions of the key exchange protocol in the presence of the adversary (this is essentially the security requirement that we introduce and formalize in this paper), and 2) the security of the protocol can be reduced to that of the primitive, no matter how the keys for the primitive are distributed. Proving that the two conditions are satisfied, and then applying our generic theorem, should be simpler than performing a monolithic analysis of the composed protocol. We exemplify our results in the case of a profile of the TLS protocol. Our definition and results are set entirely within the framework of cryptographic games (and thus avoid the use of simulation).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
nigel @ cs bris ac uk
brzuska @ cased de
marc fischlin @ gmail com
bogdan @ cs bris ac uk
2013-01-21: revised
2012-04-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {C.  Brzuska and M.  Fischlin and N. P.  Smart and B.  Warinschi and S.  Williams},
      title = {Less is More: Relaxed yet Composable Security Notions for Key Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2012/242},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.