Update of HQC

[Loïc Bidoux]

Hi all,

We have updated the specifications of HQC to improve their readability and to propose several modifications to the NIST team that we believe are worth considering for integration in the future standard. The new document is available on HQC's website: https://pqc-hqc.org.

The list of all the suggested modifications is accessible through the changelog of the document. Most suggestions are minor changes meant to align HQC specifications with design choices made in FIPS-203. We have also proposed a major modification related to the Fujisaki-Okamoto transform used to construct HQC-KEM from HQC-PKE. Indeed, it has been updated by fixing the rejection of the scheme [1], using the FO_m transform instead of the FO one (similarly to FIPS-203) and by adding (ek_KEM, salt) within K and θ derivation to improve the binding properties of HQC [2].

[1] Markku-Juhani O. Saarinen. IND-CCA2 issue in HQC. Public comment on the NIST pqc-forum mailing list, 2025.

[2] Deirdre Connolly. Improvements to consider for HQC. Public comment on the NIST pqc-forum mailing list, 2025.

Best regards,
HQC Team

[Markku-Juhani O. Saarinen]

Hi,

Thanks for the update. I also updated my simple Python HQC implementation to match the changes (and "v5.0.0" test vectors): https://github.com/mjosaarinen/hqc-py

A good practice when publishing algorithm specifications is to see if the algorithm can be implemented (in an interoperable fashion) based on the specification alone. An experienced cryptographer can do this in one or two days.

Here's an initial issue list from my check (references are to the new spec https://pqc-hqc.org/doc/hqc_specifications_2025_08_22.pdf and v5.0.0 code at https://gitlab.com/pqc-hqc/hqc/).

- The new specification and code now indeed implements implicit-rejection Fujisaki-Okamoto for IND-CCA2, much in the same manner as Kyber. Good.

- As far as I can see, the domain separation byte constants for functions I, J, G, and H (Table 1) are not documented anywhere.

- The "biased" fixed-weight sampling function GenerateRandomSupport() is implemented differently from the explanation in Section 3.2: Given a uniform input x, 0 <= x < 2^32, instead of computing x mod n (on line 2 of rand), it computes floor((x * n) / 2^32). These have different distributions -- I am not sure which version Section 6.2.3 ("Security proof with non uniform randomness sampling") is analyzing, or both.

- The new function, SampleFixedWeightVect$, used to sample the secret key (x and y) via rejection sampling, is not documented anywhere except in the source code. I reverse-engineered it from the implementation; this is more complex than it needs to be, and somewhat wasteful on XOF output (I don't understand why the implementation doesn't process XOF output with SHAKE256's block size). However, the output distribution looks right.

- There are numerous oddities -- the rejection sampler uses big-endian conversion from 3 bytes, while the biased sampler uses little-endian conversion from 4-byte chunks. An implementor can't guess things like this. I suggest stating the endianness convention in the specification and using the same endianness convention in all parts of the algorithm (preferably little-endian, as in FIPS 203 and 204).

- From an engineering perspective, it is preferable to have only one function for sampling fixed-weight vectors, and in my opinion, it should be a rejection sampler. The arguments for the biased function being "better in hardware" do not make sense to me (and I have substantial experience with PQC hardware). Clearly, only having to implement *one* function for this purpose would be preferable from a hardware perspective, and the rejection sampling variant actually seems more efficient (uses less XOF output and has simpler logic).
   
- Authors implement their own PRNG, so this implementation can't use the same KAT generation logic as other KEMs. Suggest _internal() - style interfaces for testability, as used in FIPS 203.

Cheers,

-markku

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

--
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/f417df1e97474a64a7ac09165c7750e7%40owndata.org.

[Deirdre Connolly]

These improvements are great to see! I also appreciate the improved readability of the PKE and KEM algorithms laid out in section 3.

It looks clear that as of this version, an entire HQC keypair can be derived and expanded from the new 32 byte `seed_KEM`, but that both the seed format and the fully expanded decapsulation key format `dk_KEM` are acceptable formats. While we argued for the seed format in ML-KEM, and FIPS 203 allows for both, we've discovered in the IETF and elsewhere that having two 'equally valid' formats for secret key material causes confusion and possible security vulnerabilities. 

So, can we choose just the seed_KEM format as 'the' format of the secret decapsulation key material for HQC? The expanded format that is used inside `HQC-KEM.Decaps() ` can be cached elsewhere in the implementation, but when moving key material around, especially between FIPS modules, the seed_KEM byte format would be 'the' format. The internal computations of `HQC-KEM.Keygen()` are cheaper than `Encaps()` and `Decaps()` according to the reference and optimized benchmarks in the updated submission, so while caching the expanded structures can be done, it will not strictly be necessary performance-wise. 

Having this explicitly laid out in HQC-KEM / FIPS 207 or whatever the final NIST document is would be very helpful, with either an explicit description of `HQC-KEM.Keygen()` allowing a passed-in `dk_KEM` (in the 32-byte seed format) or a separate function 'PrivatetoPublic(dk)` called by `HQC-KEM.Keygen()` to expand the passed in `dk_KEM`, including all the FIPS language necessary to make this ok and compliant and fine, would be very helpful. 

[Mike Ounsworth]

+1 to Deirdre.

Please make seed 'the' private format, and allow caching the expanded key where needed for performance reasons.

---

Mike Ounsworth

 

---

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Deirdre Connolly <durumcr...@gmail.com>
Sent: Thursday, August 28, 2025 11:28 AM
To: Loïc Bidoux <loic....@owndata.org>
Cc: pqc-...@list.nist.gov <pqc-...@list.nist.gov>
Subject: [EXTERNAL] Re: [pqc-forum] Update of HQC

 

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAFR824yRJ%3DXrEu-c5Z%3DiRLGeMo2u3E0cnESPwp%2Bs9EFgqdNGVA%40mail.gmail.com.

Any email and files/attachments transmitted with it are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

[John Mattsson]

+1 to Deirdre and Mike.

Does NIST have a preliminary name for the standardized version of HQC that is expected to appear in FIPS 207? As I am not interested in the pre-standardized version, having a name for the standardized one would be useful.

Cheers,
John

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CH0PR11MB5739743944BC95CD96021E059F3BA%40CH0PR11MB5739.namprd11.prod.outlook.com.

[Moody, Dustin (Fed)]

John,

We anticipate the name to be HQC-KEM.

Dustin

---

From: 'John Mattsson' via pqc-forum <pqc-...@list.nist.gov>
Sent: Friday, August 29, 2025 4:32 AM
To: Mike Ounsworth <Mike.Ou...@entrust.com>; Deirdre Connolly <durumcr...@gmail.com>; Loïc Bidoux <loic....@owndata.org>
Cc: pqc-forum <pqc-...@list.nist.gov>

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/GVXPR07MB9678E5DAE359BBF3A80E8CFA893AA%40GVXPR07MB9678.eurprd07.prod.outlook.com.