Paper 2019/737

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

Katriel Cohn-Gordon and Cas Cremers and Kristian Gjøsteen and Håkon Jacobsen and 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: 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.