Small update regarding HQC parameters
292 views
Skip to first unread message
Philippe Gaborit
Aug 14, 2026, 11:27:11 PM (2 days ago) Aug 14
to pqc-...@list.nist.gov, Philippe Gaborit
Dear all,
In our next update on HQC specifications which shall be released within
one month, our idea is to make a small update regarding parameters.
Regarding HQC parameters the situation is the following:
1. We know from recent papers [1] and [2] that it is possible to improve
slightly (by roughly 10%) the original DFR described in HQC proposal.
2. There has been recent generic technical optimization in [3] for
finding very low weight words which impacts HQC security on a few
bits. The attack improves the polynomial part of the complexity (and not
on the asymptotic part) see details in [3], so that in [3] the actual
Lvl 1 parameters is estimated at 139.87b in the NIST model.
3. Moreover in order to get the desirable anonymous property (which is
the case for KYBER and ML-KEM) it is sufficient that the weight of the
weight of the error $w_r$ is even ([4,5]).
The fact that there is a margin on the DFR means that we can increase
the weight w and $w_r$ (hence increasing the security) without changing
the length of the code.
In order to adjust the security of HQC to these recent technical attack
improvements, our idea is to do the following update on parameters:
Actual parameters:
Level | n | w | w_r | 2-DOOM| Anonymous | Log(DFR)
HQC-1 | 17669 | 66 | 75 | 139.87 | No | < -128
HQC-3 | 35851 | 100 | 114 | 207.28 | OK | < -192
HQC-5 | 57637 | 131 | 149 | 268.91 | No | < -256
New proposed parameters :
Level | n | w | w_r | 2-DOOM| Anonymous | Log(DFR)
HQC-1 | 17669 | 67 | 76 | 141.96 | OK | -127.75
HQC-3 | 35851 |101 | 114 | 209.38 | OK | -196
HQC-5 | 57637 |132 | 150 | 271.05 | OK | -260
New best security evaluation of attack 2-DOOM is from [3] (in the NIST
model) and DFR from [1,2].
Concretely it means increasing w and $w_r$ by 1 for Lvl 1 and 5, and w
by 1 for Lvl 3, without changing the length of the code and almost no
impact on performances. If we proceed this way it permits to get
security estimate very close to what is expected for the different
levels (for instance 141.96 rather than 143 for Lvl 1) with a DFR very
close to the expected level (-127.75 rather than -128).
On our side we believe that these previous proposed updated parameters
are sufficient to fulfill expected security criteria by the NIST.
Else another possibility would be increase n to 18443 rather than 17669,
in that case we would get w=69 and w_r=78 for a security of 146b and a
DFR of -128.6, hence overall a 4.3% raise in the size of the key and a
raise of order 10% in the performances.
[1] Antoine Mesnard, Jean-Pierre Tillich, Valentin Vasseur: The Syndrome
Weight Distribution in Quasi-Cyclic Codes, Applications to BIKE and HQC.
PQCrypto (1) 2026: 156-187
[2] Sebastian Bitzer, Jean-Christophe Deneuville, Emma Munisamy, Bharath
Purtipli, Stefan Ritterhoff, Antonia Wachter-Zeh: HQC Beyond the
Standard: Ciphertext Compression and Refined DFR Analysis. EUROCRYPT
2026: 544-574
[3] K. Carrier, V. Hatey, L. Luzzi and JP Tillich, Multilevel Amortized
Gaussian Elimination in Information-Set Decoding: Applications to HQC
and PCG (https://eprint.iacr.org/2026/1498)
[4] K. Xagawa, Anonymity of NIST PQC Round 3 KEMs, Eurocrypt, 2022.
[5] V. Maram, K. Xagawa, Post-quantum anonymity of Kyber. PKC, 2023.
best,
philippe for the HQC team
In our next update on HQC specifications which shall be released within
one month, our idea is to make a small update regarding parameters.
Regarding HQC parameters the situation is the following:
1. We know from recent papers [1] and [2] that it is possible to improve
slightly (by roughly 10%) the original DFR described in HQC proposal.
2. There has been recent generic technical optimization in [3] for
finding very low weight words which impacts HQC security on a few
bits. The attack improves the polynomial part of the complexity (and not
on the asymptotic part) see details in [3], so that in [3] the actual
Lvl 1 parameters is estimated at 139.87b in the NIST model.
3. Moreover in order to get the desirable anonymous property (which is
the case for KYBER and ML-KEM) it is sufficient that the weight of the
weight of the error $w_r$ is even ([4,5]).
The fact that there is a margin on the DFR means that we can increase
the weight w and $w_r$ (hence increasing the security) without changing
the length of the code.
In order to adjust the security of HQC to these recent technical attack
improvements, our idea is to do the following update on parameters:
Actual parameters:
Level | n | w | w_r | 2-DOOM| Anonymous | Log(DFR)
HQC-1 | 17669 | 66 | 75 | 139.87 | No | < -128
HQC-3 | 35851 | 100 | 114 | 207.28 | OK | < -192
HQC-5 | 57637 | 131 | 149 | 268.91 | No | < -256
New proposed parameters :
Level | n | w | w_r | 2-DOOM| Anonymous | Log(DFR)
HQC-1 | 17669 | 67 | 76 | 141.96 | OK | -127.75
HQC-3 | 35851 |101 | 114 | 209.38 | OK | -196
HQC-5 | 57637 |132 | 150 | 271.05 | OK | -260
New best security evaluation of attack 2-DOOM is from [3] (in the NIST
model) and DFR from [1,2].
Concretely it means increasing w and $w_r$ by 1 for Lvl 1 and 5, and w
by 1 for Lvl 3, without changing the length of the code and almost no
impact on performances. If we proceed this way it permits to get
security estimate very close to what is expected for the different
levels (for instance 141.96 rather than 143 for Lvl 1) with a DFR very
close to the expected level (-127.75 rather than -128).
On our side we believe that these previous proposed updated parameters
are sufficient to fulfill expected security criteria by the NIST.
Else another possibility would be increase n to 18443 rather than 17669,
in that case we would get w=69 and w_r=78 for a security of 146b and a
DFR of -128.6, hence overall a 4.3% raise in the size of the key and a
raise of order 10% in the performances.
[1] Antoine Mesnard, Jean-Pierre Tillich, Valentin Vasseur: The Syndrome
Weight Distribution in Quasi-Cyclic Codes, Applications to BIKE and HQC.
PQCrypto (1) 2026: 156-187
[2] Sebastian Bitzer, Jean-Christophe Deneuville, Emma Munisamy, Bharath
Purtipli, Stefan Ritterhoff, Antonia Wachter-Zeh: HQC Beyond the
Standard: Ciphertext Compression and Refined DFR Analysis. EUROCRYPT
2026: 544-574
[3] K. Carrier, V. Hatey, L. Luzzi and JP Tillich, Multilevel Amortized
Gaussian Elimination in Information-Set Decoding: Applications to HQC
and PCG (https://eprint.iacr.org/2026/1498)
[4] K. Xagawa, Anonymity of NIST PQC Round 3 KEMs, Eurocrypt, 2022.
[5] V. Maram, K. Xagawa, Post-quantum anonymity of Kyber. PKC, 2023.
best,
philippe for the HQC team
D. J. Bernstein
Aug 15, 2026, 5:47:05 AM (2 days ago) Aug 15
to pqc-...@list.nist.gov
It's weird to see a proposal of a slight change in parameters as a snap
reaction to a new paper claiming an attack speedup. If the paper is
wrong (see below), does the proposal go away? If the paper is right,
does the next paper mean another change in parameters?
Stability is useful. For proactively defending against potential attack
speedups, it's better to have a larger security margin. So why not just
scrap HQC-128 and leave HQC-192 alone? Are there applications that can
afford HQC-128 but not HQC-192? For applications that can afford more
security margin, why not add something bigger than HQC-256?
I understand that there's a separate argument to change HQC-256 enc for
"anonymity" (currently an HQC-256 ciphertext reveals the parity of the
public key it's being sent to), but is that better than changing HQC-256
keygen for the same purpose? I also realize that previous test vectors
are being thrown away because of other changes, but there's still
nonzero value in retaining parameter sets.
Philippe Gaborit writes:
> There has been recent generic technical optimization in [3] for finding
> very low weight words which impacts HQC security on a few bits.
No, [3] (eprint 2026/1498) is a regression from prior work; it does not
decrease attack costs.
[3] says that it saves a few bits compared to Stern's 1988 algorithm by
speeding up row reduction, specifically by exchanging a limited number
of positions in the information set at each step rather than generating
a completely new information set at each step.
BLP2008 already did that, and did so in a more streamlined way, using a
chain rather than a tree. A tree doesn't add more randomness per step;
it just consumes memory and complicates the Markov-chain analysis.
[3] doesn't include BLP2008 in its comparison tables. [3] makes the
following claim: "A first approach, proposed by Canteaut and Chabaud
[13], and later refined by Bernstein, Lange and Peters [7], updates the
information set by exchanging only one coordinate between consecutive
iterations. This reduces the cost of Gaussian elimination from cubic to
quadratic but introduces strong dependencies between successive
iterations, which offset the expected linear speedup in the sublinear
regime."
The "only one coordinate" and "strong dependencies" descriptions are
correct for Canteaut--Chabaud (and Canteaut--Sendrier and earlier Omura)
but not for BLP2008 ("[7]"). BLP2008 exchanges several positions at a
time, not just one, to optimize overall performance. The resulting
dependencies are quantified with a Markov-chain analysis in BLP2008 and,
after optimization, are minor.
Meanwhile [3] misses the further linear-algebra speedups from the CAT
paper. Only 10% of the bit operations are spent on linear algebra in the
CAT results for HQC-128 (single-target; multi-target should be smaller).
[3] claims to use a "consistent logic-gate cost model" as in the CAT
paper; [3] estimates "approximately 140 bits" for HQC-128, "about 3 bits
below its NIST security target". This comparison is flawed on multiple
levels:
* The CAT paper counts traditional 2-input logic gates and provides
software to _check_ claimed gate counts. [3] does not, in fact,
count traditional gates, nor does [3] check its gate counts.
* [3] instead postulates, e.g., "log_2(N) (b + log_2(N))" gates for
"RAM_2(b,N)", which is "accessing b consecutive bits in a memory
containing N bits". There are unsupported claims that this
postulate "accounts for" memory-lookup costs and is "commonly
considered". Nowhere does [3] provide a definition of a gate set,
let alone counting gates according to that definition.
* Meanwhile NIST's 2^143 was at least _trying_ to estimate logic
gates for AES-128 attacks with the most common concept of gates,
although NIST (1) ended up somewhat overestimating this (see
Section 5 of the CAT paper) and (2) later switched to allowing a
"one-bit memory read or write" as a single gate---which allows
even faster AES-128 attacks (see Appendix D of the CAT paper).
See also https://eprint.iacr.org/2024/1076.
Readers hearing that HQC-128 has dropped below its security target think
that there must have been an attack speedup against HQC-128, but what's
happening in [3] is just random noise from estimating costs differently.
---D. J. Bernstein
reaction to a new paper claiming an attack speedup. If the paper is
wrong (see below), does the proposal go away? If the paper is right,
does the next paper mean another change in parameters?
Stability is useful. For proactively defending against potential attack
speedups, it's better to have a larger security margin. So why not just
scrap HQC-128 and leave HQC-192 alone? Are there applications that can
afford HQC-128 but not HQC-192? For applications that can afford more
security margin, why not add something bigger than HQC-256?
I understand that there's a separate argument to change HQC-256 enc for
"anonymity" (currently an HQC-256 ciphertext reveals the parity of the
public key it's being sent to), but is that better than changing HQC-256
keygen for the same purpose? I also realize that previous test vectors
are being thrown away because of other changes, but there's still
nonzero value in retaining parameter sets.
Philippe Gaborit writes:
> There has been recent generic technical optimization in [3] for finding
> very low weight words which impacts HQC security on a few bits.
decrease attack costs.
[3] says that it saves a few bits compared to Stern's 1988 algorithm by
speeding up row reduction, specifically by exchanging a limited number
of positions in the information set at each step rather than generating
a completely new information set at each step.
BLP2008 already did that, and did so in a more streamlined way, using a
chain rather than a tree. A tree doesn't add more randomness per step;
it just consumes memory and complicates the Markov-chain analysis.
[3] doesn't include BLP2008 in its comparison tables. [3] makes the
following claim: "A first approach, proposed by Canteaut and Chabaud
[13], and later refined by Bernstein, Lange and Peters [7], updates the
information set by exchanging only one coordinate between consecutive
iterations. This reduces the cost of Gaussian elimination from cubic to
quadratic but introduces strong dependencies between successive
iterations, which offset the expected linear speedup in the sublinear
regime."
The "only one coordinate" and "strong dependencies" descriptions are
correct for Canteaut--Chabaud (and Canteaut--Sendrier and earlier Omura)
but not for BLP2008 ("[7]"). BLP2008 exchanges several positions at a
time, not just one, to optimize overall performance. The resulting
dependencies are quantified with a Markov-chain analysis in BLP2008 and,
after optimization, are minor.
Meanwhile [3] misses the further linear-algebra speedups from the CAT
paper. Only 10% of the bit operations are spent on linear algebra in the
CAT results for HQC-128 (single-target; multi-target should be smaller).
[3] claims to use a "consistent logic-gate cost model" as in the CAT
paper; [3] estimates "approximately 140 bits" for HQC-128, "about 3 bits
below its NIST security target". This comparison is flawed on multiple
levels:
* The CAT paper counts traditional 2-input logic gates and provides
software to _check_ claimed gate counts. [3] does not, in fact,
count traditional gates, nor does [3] check its gate counts.
* [3] instead postulates, e.g., "log_2(N) (b + log_2(N))" gates for
"RAM_2(b,N)", which is "accessing b consecutive bits in a memory
containing N bits". There are unsupported claims that this
postulate "accounts for" memory-lookup costs and is "commonly
considered". Nowhere does [3] provide a definition of a gate set,
let alone counting gates according to that definition.
* Meanwhile NIST's 2^143 was at least _trying_ to estimate logic
gates for AES-128 attacks with the most common concept of gates,
although NIST (1) ended up somewhat overestimating this (see
Section 5 of the CAT paper) and (2) later switched to allowing a
"one-bit memory read or write" as a single gate---which allows
even faster AES-128 attacks (see Appendix D of the CAT paper).
See also https://eprint.iacr.org/2024/1076.
Readers hearing that HQC-128 has dropped below its security target think
that there must have been an attack speedup against HQC-128, but what's
happening in [3] is just random noise from estimating costs differently.
---D. J. Bernstein
John Mattsson
Aug 15, 2026, 2:44:34 PM (2 days ago) Aug 15
to Philippe Gaborit, pqc-...@list.nist.gov, Philippe Gaborit
Hi Philippe,
I agree that HQC-KEM should be updated to provide the anonymity property.
Might I ask what the purpose is of releasing a new HQC specification now, when NIST is expected to publish FIPS 207 soon? Are the proposed changes aligned with FIPS 207? Do you not expect FIPS 207 IPD to be published soon?
Once the FIPS 207 IPD is published, I don't think the pqc-hqc.org specification should be used for anything other than historical reference and potentially explanatory purposes.
The situation is different for Classic McEliece and FrodoKEM, where the paywalled standards should be considered cybersecurity risks and should never be used.
---
One comment: The bullet list in Section 3.4.2 seems to state that the minimum distance d_min for RS-S3 is 49, but
δ = 29, and 2δ + 1 = 59. Please ignore this if I am misunderstanding something.
Cheers,
John Preuß Mattsson
LJEPOSAVA DIMITRIJEVIC
Aug 16, 2026, 3:30:19 PM (12 hours ago) Aug 16
to pqc-forum, John Mattsson, Philippe Gaborit
LJEPOSAVA DIMITRIJEVIC
Aug 16, 2026, 3:31:38 PM (12 hours ago) Aug 16
to pqc-forum, LJEPOSAVA DIMITRIJEVIC, John Mattsson, Philippe Gaborit
Reply all
Reply to author
Forward
0 new messages