Multi-User CDH Problems and the Concrete Security of NAXOS and HMQV

Eike Kiltz; Jiaxin Pan; Doreen Riepel; Magnus Ringerud

Paper 2023/115

Multi-User CDH Problems and the Concrete Security of NAXOS and HMQV

Eike Kiltz

, Ruhr University Bochum

Jiaxin Pan

, Norwegian University of Science and Technology

Doreen Riepel

, Ruhr University Bochum

Magnus Ringerud

, Norwegian University of Science and Technology

Abstract

We introduce CorrGapCDH, the Gap Computational Diffie-Hellman problem in the multi-user setting with Corruptions. In the random oracle model, our assumption tightly implies the security of the authenticated key exchange protocols NAXOS in the eCK model and (a simplified version of) X3DH without ephemeral key reveal. We prove hardness of CorrGapCDH in the generic group model, with optimal bounds matching the one of the discrete logarithm problem. We also introduce CorrCRGapCDH, a stronger Challenge-Response variant of our assumption. Unlike standard GapCDH, CorrCRGapCDH implies the security of the popular AKE protocol HMQV in the eCK model, tightly and without rewinding. Again, we prove hardness of CorrCRGapCDH in the generic group model, with (almost) optimal bounds. Our new results allow implementations of NAXOS, X3DH, and HMQV without having to adapt the group sizes to account for the tightness loss of previous reductions. As a side result of independent interest, we also obtain modular and simple security proofs from standard GapCDH with tightness loss, improving previously known bounds.

Note: Discuss and fix an issue in the GGM proof. Bounds and results remain the same.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. CT-RSA
Keywords: Authenticated key exchange HMQV NAXOS X3DH generic hardness
Contact author(s): eike kiltz @ rub de
jiaxin pan @ ntnu no
doreen riepel @ rub de
magnus ringerud @ ntnu no
History: 2023-07-05: revised; 2023-01-31: received; See all versions
Short URL: https://ia.cr/2023/115
License: CC BY

BibTeX

@misc{cryptoeprint:2023/115,
      author = {Eike Kiltz and Jiaxin Pan and Doreen Riepel and Magnus Ringerud},
      title = {Multi-User {CDH} Problems and the Concrete Security of {NAXOS} and {HMQV}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/115},
      year = {2023},
      url = {https://eprint.iacr.org/2023/115}
}