Paper 2023/854

On Optimal Tightness for Key Exchange with Full Forward Secrecy via Key Confirmation

Kai Gellert, University of Wuppertal
Kristian Gjøsteen, Norwegian University of Science and Technology
Håkon Jacobsen, University of Oslo, Thales Norway
Tibor Jager, University of Wuppertal

A standard paradigm for building key exchange protocols with full forward secrecy (and explicit authentication) is to add key confirmation messages to an underlying protocol having only weak forward secrecy (and implicit authentication). Somewhat surprisingly, we show through an impossibility result that this simple trick must nevertheless incur a linear tightness loss in the number of parties for many natural protocols. This includes Krawczyk's HMQV protocol (CRYPTO 2005) and the protocol of Cohn-Gordon et al. (CRYPTO 2019). Cohn-Gordon et al. gave a very efficient underlying protocol with weak forward secrecy having a linear security loss, and showed that this is optimal for certain reductions. However, they also claimed that full forward secrecy could be achieved by adding key confirmation messages, and without any additional loss. Our impossibility result disproves this claim, showing that their approach, in fact, has an overall quadratic loss. Motivated by this predicament we seek to restore the original linear loss claim of Cohn-Gordon et al. by using a different proof strategy. Specifically, we start by lowering the goal for the underlying protocol with weak forward secrecy, to a selective security notion where the adversary must commit to a long-term key it cannot reveal. This allows a tight reduction rather than a linear loss reduction. Next, we show that the protocol can be upgraded to full forward secrecy using key confirmation messages with a linear tightness loss, even when starting from the weaker selective security notion. Thus, our approach yields an overall tightness loss for the fully forward-secret protocol that is only linear, as originally claimed. Finally, we confirm that the underlying protocol of Cohn-Gordon et al. can indeed be proven selectively secure, tightly.

Note: Uploaded the full version of the paper. The proof of the impossibility result (Theorem 6.4) has been slightly simplified compared to the conference version (Theorem 2). 2024-02-21: Fixed a flaw in the definition of selective key security.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2023
Key exchange protocolstightnessmeta-reductions
Contact author(s)
kai gellert @ uni-wuppertal de
kristian gjosteen @ ntnu no
hakon jacobsen @ its uio no
jager @ uni-wuppertal de
2024-02-21: last of 3 revisions
2023-06-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kai Gellert and Kristian Gjøsteen and Håkon Jacobsen and Tibor Jager},
      title = {On Optimal Tightness for Key Exchange with Full Forward Secrecy via Key Confirmation},
      howpublished = {Cryptology ePrint Archive, Paper 2023/854},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.