B3DH: A Drop-In Optimization of Triple Diffie-Hellman Key Exchange Protocols Maintaining Tight Security Bound

The triple Diffie–Hellman (3DH) authenticated key exchange protocol is widely adopted in practice due to its simplicity and strong performance. It is employed, for instance, in the Noise framework, Signal, and WhatsApp. This protocol requires four exponentiations per endpoint and only a single round of communication, during which Alice and Bob each exchange a single group element, while providing a (weakened) form of forward secrecy. At CRYPTO 2019, Cohn-Gordon et al. provided a proof with optimal tightness for this protocol under the SDH assumption in the ROM, allowing for further performance improvements by choosing optimal security parameters. In this paper, we show that even greater efficiency can be achieved by introducing Batched-3DH (B3DH), a variant of 3DH that requires only three exponentiations, while admitting a security proof as tight as that of Cohn-Gordon et al. under the same assumptions. The only difference from 3DH lies in the computation of the initial shared key prior to key derivation; in particular, the long-term keys, as well as the interaction between Alice and Bob, remain unchanged, meaning that practical protocols built on 3DH can be readily adapted to B3DH. Finally, we implement B3DH and compare its efficiency with that of standard 3DH, showing that the practical performance gain closely matches the theoretical improvement of 25 percent when operations other than exponentiations are neglected.