International Association for Cryptologic Research

International Association
for Cryptologic Research


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 , Thales Norway and University of Oslo
Tibor Jager , University of Wuppertal
DOI: 10.1007/978-3-031-38551-3_10 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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 can be achieved via key confirmation without any additional loss. Our impossibility result disproves this claim, showing that their approach, in fact, has an overall loss which is quadratic. Motivated by this predicament we seek to restore the original lin- ear 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.
  title={On Optimal Tightness for Key Exchange with Full Forward Secrecy via Key Confirmation},
  author={Kai Gellert and Kristian Gjøsteen and Håkon Jacobsen and Tibor Jager},