Improvements to consider for HQC

[Deirdre Connolly]

Hello pqc-forum,

On the announcement of the selection of HQC as the Round Four finalist, I surveyed its binding properties and wrote them up here. This leans heavily on the proofs and analysis in https://eprint.iacr.org/2024/1233.pdf, but also Peter Cambell at NCSC pointed out some gaps in that paper as well. 

The takeaway is that the design of HQC as specified in the Round Four submission updated February 19 2025 does not have great binding properties, and lacks even HON-BIND-K-CT. It does appear to achieve HON-BIND-K-PK. This is a big step down from the properties provided by ML-KEM, especially when using the seed variant. 

Some changes to consider that would improve this:

A: Include the PKE salt in the KEM KDF hash.

The salt, which is part of the KEM ciphertext but not committed to, can be manipulated such that the same shared secret will result from implicit rejection of multiple different invalid ciphertexts.

B: Include the public encapsulation key in the KEM KDF hash.

Currently, without commiting to the encapsulation key, an attacker can use the FO transform implicit-rejection value of one KEM keypair as the 'random' message being encrypted by the PKE, and decapsulate under another keypair: this results in the same shared secret even though the PKE scheme rejects the ciphertext.

I haven't looked further at the implications of doing both of these together but hopefully we could do both. If anyone is looking further at changes like this for HQC I'd love to read more.

Cheers and thank you,

Deirdre

[Patrick Struck]

Dear all,

an updated version of our paper 'Binding Security of Implicitly-Rejecting KEMs and Application to BIKE and HQC' is now available as ePrint 2024/1233. We addressed the gaps pointed out by Peter Cambell and Deirdre Connolly—thank you for bringing them to our attention!

Best
Patrick, Maxi, and Juliane

[Deirdre Connolly]

Awesome!