CryptoDB
On Optimal Tightness for Key Exchange with Full Forward Secrecy via Key Confirmation
| Authors: |
|
|---|---|
| Download: |
|
| 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. |
BibTeX
@inproceedings{crypto-2023-33167,
title={On Optimal Tightness for Key Exchange with Full Forward Secrecy via Key Confirmation},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-38551-3_10},
author={Kai Gellert and Kristian Gjøsteen and Håkon Jacobsen and Tibor Jager},
year=2023
}