HQC: Proposal for Hardening Decapsulation against Faulty Implementations through Confirmation Codes

[Felix Günther]

Dear pqc-forum,

Following up on our presentation at the NIST Workshop on Guidance for
KEMs and supporting discussions there and since, we wanted to bring the
following proposal to the list.

The proposal is to harden HQC against faulty implementations of the
FO-style decapsulation which skip/incorrectly implement the
re-encryption step, like the bug in HQC's reference and liboqs
implementations (CVE-2024-54137). In our recent work [1, to appear at
Crypto 2025], we show how a small 'confirmation code' output by PKE
encryption and included in the KEM key derivation can mitigate such
risk, surfacing faulty implementations with basic correctness tests.

Concretely for HQC, we show that using only 1 byte of confirmation code
(from the truncated-away \ell bits when computing v) would have caught
HQC's implementation bug. Hashing this extra byte comes at negligible
cost (<= 0.25% overhead in our unoptimized experiments). For details,
see Section 5.2 of our paper [1].

We want to propose integrating such confirmation code into NIST's
upcoming standard for HQC. We'd be happy to discuss and hear your
feedback on this proposal.

Thanks and best regards,
Felix (with Lewis, Kathrin, and Douglas)


[1] Glabush, Günther, Hövelmanns, Stebila. Verifiable Decapsulation:
Recognizing Faulty Implementations of Post-Quantum KEMs.
https://eprint.iacr.org/2025/450 (to appear at Crypto 2025)

[Bobby McGee]

IMHO, adding something like these confirmation codes is a good idea.  At the moment, there is no way to verify that a decapsulation instance implemented the FO transform correctly or at all except faith or maybe throwing negative test vectors at everyone you want to talk to.  The FO is important enough to deserve proof that it was actually implemented and implemented correctly.  I can imagine bad actors pinging everyone with faulty ciphertexts, finding bad implementations, and exploiting them.  Baking evidence that the implementation isn't faulty into the shared key seems like a good idea to me.

[Loïc Bidoux]

Dear Felix, Lewis, Kathrin and Douglas,

Thank you for sharing your work on confirmation codes for KEM. We find it very interesting as the proposed modification has a rather small impact on HQC’s design while targeting a part of the implementation that can easily go unnoticed when implemented poorly. Nonetheless, we did not integrate it in our recent update as we don’t think that the protocol design should be modified to accommodate potential shortcomings of its implementation. Instead, we are planning to release a set of unit tests that a proper implementation of the standard (once ready) should pass as guidance for implementers. That being said, we don’t have a strong opinion on this topic and would understand should the NIST team decide otherwise.

Best regards,
HQC Team

---

De : pqc-...@list.nist.gov <pqc-...@list.nist.gov> de la part de Bobby McGee <janewayki...@gmail.com>
Envoyé : jeudi 12 juin 2025 16:28
À : pqc-forum
Cc : Felix Günther
Objet : [pqc-forum] Re: HQC: Proposal for Hardening Decapsulation against Faulty Implementations through Confirmation Codes

 

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/bf69b14f-c4b7-4d90-b0d2-a12ba3614654n%40list.nist.gov.