Berkant Ustaoğlu

Ust08 errata

Obtaining a secure and efficient key agreement protocol from (H)MQV and NAXOS
Berkant Ustaoğlu
Files & links
BibTeX, doi, pdf, extended version, about

LaMacchia, Lauter and Mityagin recently presented a strong security definition for authenticated key agreement strengthening the well-known Canetti-Krawczyk definition. They also described a protocol, called NAXOS, that enjoys a simple security proof in the new model. Compared to MQV and HMQV, NAXOS is less efficient and cannot be readily modified to obtain a one-pass protocol. On the other hand MQV does not have a security proof, and the HMQV security proof is extremely complicated.

This paper proposes a new authenticated key agreement protocol, called CMQV (‘Combined’ MQV), which incorporates design principles from MQV, HMQV and NAXOS. The new protocol achieves the efficiency of HMQV and admits a natural one-pass variant. Moreover, we present a relatively simple and intuitive proof that CMQV is secure in the LaMacchia-Lauter-Mityagin model.

key agreement protocols, MQV, provable security
The errata is with respect to the version published in Designs, Codes and Cryptography. The local pdf file and the ePrint report are updated to account for these errors.
In Table 2, efficiency of (H,C)MQV over elliptic curves of prime or nearly prime order should be 2.17 exponentiations instead of 2.25; for the DSA groups CMQV and MQV achieve 3.17 instead of 3.25. The comparison of the protocols is not affected. The error is due to an incorrect estimate of Shamir's trick - Algorithm 14.88 of the Handbook of Applied Cryptography.
The journal version of this paper a session identifier S is given by (AA,BB,X,Y) with matching session S* given by (BB,AA,Y,X). These identifiers differ from the original eCK definition: they do not carry information about the role of session owners and hence both parties AA and BB may view themselves as an initiator. If both parties perform the protocol as an initiator, then sessions S and S* even though matching do not compute the same session key, since the order of identities and public keys used in the key derivation function is reversed.