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

##### 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.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. CT-RSA
Keywords
Authenticated key exchangeHMQVNAXOSX3DHgeneric hardness
Contact author(s)
eike kiltz @ rub de
jiaxin pan @ ntnu no
doreen riepel @ rub de
magnus ringerud @ ntnu no
History
2023-02-01: approved
See all versions
Short URL
https://ia.cr/2023/115

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},
note = {\url{https://eprint.iacr.org/2023/115}},
url = {https://eprint.iacr.org/2023/115}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.