Paper 2019/737

Highly Efficient Key Exchange Protocols with Optimal Tightness -- Enabling real-world deployments with theoretically sound parameters

Katriel Cohn-Gordon, Cas Cremers, Kristian Gjøsteen, Håkon Jacobsen, and Tibor Jager


In this paper we give nearly tight reductions for modern implicitly authenticated Diffie-Hellman protocols in the style of the Signal and Noise protocols, which are extremely simple and efficient. Unlike previous approaches, the combination of nearly tight proofs and efficient protocols enables the first real-world instantiations for which the parameters can be chosen in a theoretically sound manner, i.e., according to the bounds of the reductions. Specifically, our reductions have a security loss which is only linear in the number of users $\mu$ and constant in the number of sessions per user $\ell$. This is much better than most other key exchange proofs which are typically quadratic in the product $\mu \ell$. Combined with the simplicity of our protocols, this implies that our protocols are more efficient than the state of the art when soundly instantiated. We also prove that our security proofs are optimal: a linear loss in the number of users is unavoidable for our protocols for a large and natural class of reductions.

Note: Corrected two errors in our security models. The first correction removes the restriction that an adversary could not interact with a session oracle after corrupting its long-term key. This effectively made it impossible for the adversary to carry out KCI attacks. Note that the proofs were always written with the updated semantic in mind, and remain unchanged. The second correction changes the EA definition to rely on matching conversations instead of partnering. The previous version trivially made any protocol insecure in the model. Thanks to Paul Rösler for identifying this issue.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2019
AKEprovable securitytightnessmeta-reductions
Contact author(s)
tibor jager @ upb de
cas cremers @ gmail com
jacobseh @ mcmaster ca
me @ katriel co uk
kristian gjosteen @ ntnu no
2019-10-12: last of 2 revisions
2019-06-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Katriel Cohn-Gordon and Cas Cremers and Kristian Gjøsteen and Håkon Jacobsen and Tibor Jager},
      title = {Highly Efficient Key Exchange Protocols with Optimal Tightness -- Enabling real-world deployments with theoretically sound parameters},
      howpublished = {Cryptology ePrint Archive, Paper 2019/737},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.