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
Tibor Jager
Abstract

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: 12.10.2019: 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. 16.08.2023: The proof of Theorem 6 is wrong. See https://eprint.iacr.org/2023/854 for a resolution and further details.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2019
Keywords
AKEprovable securitytightnessmeta-reductions
Contact author(s)
jacobsen haakon @ gmail com
History
2023-08-16: last of 3 revisions
2019-06-21: received
See all versions
Short URL
https://ia.cr/2019/737
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/737,
      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},
      url = {https://eprint.iacr.org/2019/737}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.