Simple Power Analysis of Polynomial Multiplication in HQC
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.
Nadia: We're looking at the paper: "Simple Power Analysis of Polynomial Multiplication in HQC".
Elias: Here's the gist of the paper. The single-trace Simple Power Analysis (SPA) attack against HQC exploits power consumption leakage during polynomial multiplication at the beginning of HQC decryption to recover a significant portion of the private key Attack Target and Context The paper presents a single-trace simple power analysis (SPA) attack against the Hamming Quasi-Cyclic (HQC) cryptosystem which exploits power consumption leakage that occurs during polynomial multiplication performed at the beginning of HQC decryption.
Nadia: The goal of this attack is to recover the private key by analyzing power consumption during polynomial multiplication that is performed at the beginning of HQC decryption.
Elias: The target implementation for this attack is the Additional implementation of HQC included in the NIST Round 4 submission.
Nadia: This target implementation is particularly relevant as it is included in both the PQClean and liboqs libraries.
Title and authors: Nadia: So we're talking about this paper now titled Simple Power Analysis of Polynomial Multiplication in HQC. It’s really about exploiting power leakage during polynomial multiplication right at the start of HQC decryption to pull out a piece of the private key.
Elias: Yeah, and they’re focusing on the specific implementation used in both PQClean and liboqs, which is important for anyone working with these post-quantum systems. This attack targets how that multiplication is done using a recursive Karatsuba algorithm.
Priya: So what exactly is the core problem here? Is this just a theoretical weakness, or are we talking about something practical that an attacker can actually use against real hardware?
Nadia: It's practical, Priya. They use the ChipWhisperer-Lite board to measure power traces and they found a success rate of ninety-nine point six nine percent over ten thousand attack attempts <ref:2601.07634#pg1>. That’s a really high number for a single trace analysis; it shows this is quite effective when you get the right conditions.
Elias: The specific vulnerability they're hitting is in the base-case sixty-four-bit multiplication algorithm that gets used after the Karatsuba recursion hits sixty-four bits <ref:2601.07634#pg3,base-case 64-bit multiplication algorithm>. They find that by repeating this attack on different parts, or limbs, of the private key polynomial, you can potentially recover the entire private key.
Priya: So if I'm just listening to this, what does that mean for my data security? Am I worried about something leaking during standard HQC operations?
Nadia: It means if someone can get a single power trace of the decryption process, they can get a significant portion of that private key. They aren't just looking at one spot; they are analyzing how the multiplication looks—specifically, by observing a noticeable drop between neighboring peaks in the measurement record to figure out four bits of that key limb.
Elias: And what’s interesting is that their analysis shows all their errors come from just those first four bits of the key limb, and only when those bits are zero or fifteen. That gives them a very specific pattern to look for.
Priya: That specificity is helpful, but I wonder how strong this attack really is against real-world defenses. Are these findings based on an implementation that's actually hardened?
Title and authors: Nadia: They tested their countermeasures, and they found that reducing the size of the lookup table to just one by using 'b' itself was a way to slow things down a bit, but they also mentioned removing a cache timing attack countermeasure and replacing it with classical masking.
Elias: And on the performance side, they measured how much slower these defenses made things compared to the original implementation. They found that their protected functions, base mul2 and base mul3, were significantly faster than the original base mul function.
Priya: Faster is good for performance in general, but if it means we have to use more complex masking techniques just to stop a power analysis attack, what’s the trade-off?
Nadia: The paper shows that base mul2 was about two point three times faster than base mul, and base mul3 was about six point nine times faster. So you get a big speed boost while trying to stay protected from this specific SPA attack.
Elias: But they also noted a caveat in their testing; they said the masking technique is effective for stopping the attack, but it might still allow an attacker to recover both the masked value of that key limb and the mask itself.
Priya: So if we implement these new multiplication functions, base mul2 or base mul3, are we guaranteed protection against this specific SPA method? Or is there another way they could attack it?
Nadia: The paper implies that by implementing those specific improved functions, you can be resistant to the proposed SPA attack while still getting a performance advantage over the standard setup. They are showing how to make it faster and safer at the same time.
Elias: In this work, they propose classical masking techniques specifically Boolean masking to protect private key values during those multiplication steps in HQC decryption. This allows for computation while obscuring the actual values being processed from power analysis attacks.
Priya: That sounds like a solid defense mechanism because it's based on established ideas, but I still have to wonder about the complexity of implementing that masking correctly across all the polynomial multiplication steps.
Nadia: Exactly. They did test these improved functions against ten million calls and they showed they were resistant to their SPA attack while offering that performance benefit we just talked about.
Title and authors: Elias: Overall, this paper, "Simple Power Analysis of Polynomial Multiplication in HQC," presents a new single-trace simple power analysis attack that recovers a significant portion of the private key with a ninety-nine point six nine percent success rate.
Priya: It’s interesting how they focused on just one part of the decryption process—the polynomial multiplication at the very beginning—to get away with this level of recovery.
Nadia: That focus is what makes it simple, Priya; it isolates a specific mathematical operation and shows that even in post-quantum cryptography, power leakage can reveal key material if the implementation isn't careful.
Elias: They also introduced new multiplication functions, base mul2 and base mul3, which they show are resistant to this proposed SPA attack while still offering significant performance advantages over the original implementation.
Priya: So, if we look at what this means for the next few years in PQC development, are we going to need to bake these kinds of specific countermeasure evaluations directly into every cryptographic primitive?
Nadia: It suggests that analyzing those specific multiplication routines—the Karatsuba algorithm implementation, for instance—is a necessary step when hardening any new standard like HQC.
Elias: They're also exploring the application of classical masking techniques like Boolean masking to protect private key values during those multiplication steps in HQC decryption, which is a concrete defense they put forward.
Priya: I'm still thinking about what they didn't cover deeply—how much effort it takes to truly secure that masking against sophisticated side-channel attacks beyond this specific SPA test.
Nadia: They flagged that the masking technique might still allow an attacker to recover both the masked value of a and the mask value, which is a fair limitation they pointed out.
Elias: So, in conclusion, this paper on Simple Power Analysis of Polynomial Multiplication in HQC shows how a single trace can recover ninety-nine point six nine percent of the private key with their ten thousand attempts <ref:2601.07634#pg1,Simple Power Analysis of Polynomial Multiplication in HQC>.
Priya: It’s a stark reminder that even when we have these new post-quantum algorithms, the physical implementation details are just as vulnerable as the math itself.
Nadia: That's right, it shows that focusing on how polynomial multiplication is actually coded is crucial for security in this area.
The paper's summary: Nadia: So, to put it simply, this paper shows that you can take just one power trace during the very first step of HQC decryption and pull out a chunk of the private key.
Elias: Yeah, they’re looking at that initial polynomial multiplication right where everything starts happening. It targets the specific way this multiplication is done using a recursive Karatsuba algorithm.
Priya: So, what does that actually mean for us? Is this just a theoretical weakness, or can someone actually use this against real hardware?
Nadia: It’s practical because they used actual hardware, the ChipWhisperer-Lite board. and they got a success rate of ninety-nine point six nine percent over ten thousand tries. that’s high enough to show it works when you get the right conditions.
Elias: The paper focuses on recovering a specific part of the private key polynomial, the value of y, by analyzing how power consumption changes during that multiplication process.
Priya: If they can recover a significant portion of the key from just one trace, that’s pretty alarming for anyone using this system. what are the numbers on what they found?
Nadia: They found that all their errors come from just the first four bits of that key piece, and specifically only when those bits are zero or fifteen. it gives them a very clear pattern to look for in the measurement record.
Elias: That specific pattern is what makes it simple for the attack; you watch for a noticeable drop between two neighboring peaks in the power trace to figure out those four bits.
Priya: So, this tells us that the implementation details of how they coded that multiplication routine are actually very exposed to this kind of physical analysis.
Nadia: Exactly; it shows that even in post-quantum cryptography like HQC, focusing on just one mathematical operation at the start of decryption can lead to a big portion of the secret key being recovered.
Elias: They’re not just finding a flaw; they’re proposing solutions too, introducing new multiplication functions called base mul2 and base mul3 that are resistant to this power analysis attack.
Priya: So the authors are showing us how to make it faster while also trying to stop this specific type of side-channel leakage. what’s the performance trade-off there?
Nadia: They found that base mul2 was about two point three times faster than the original base mul, and base mul3 was about six point nine times faster. it means you get a significant speed boost while trying to stay protected from this SPA attack.
Elias: But they also admitted that the masking technique they introduced might still let an attacker recover both the masked value of that key piece and the mask itself, which is a limitation they pointed out.
Priya: That’s a real caveat; so even with these new functions and masking, there’s still some room for improvement in security against more advanced attacks.
Nadia: True. the paper proves this single-trace SPA attack works well against the specific implementation they were testing, but it highlights that you need to be careful about which parts of the algorithm you try to protect.
Elias: In short, this work confirms that a simple power analysis can recover a large piece of the private key from polynomial multiplication in HQC if not properly protected. and now we look at how these new functions attempt to fix it.
The paper's improvements: Tom: So, to recap, the paper didn't just show a vulnerability; they also suggested ways to fight it by creating new multiplication functions that are harder to attack and using classical masking techniques.
Nadia: Yeah, they developed these new functions base mul2 and base mul3 which are resistant to the simple power analysis attack while still being much faster than the original implementation.
Elias: The idea is that you get this significant performance advantage without introducing timing vulnerabilities that an attacker could exploit during those multiplication steps.
Priya: So they’re trying to find that sweet spot between having a secure, masked calculation and actually getting a usable speed boost for the system. what does the masking technique actually do here?
Nadia: They implemented Boolean masking, which is a classical method to protect private key values during those multiplication steps by obscuring the actual values being processed from power analysis attacks.
Elias: It’s an established concept, but they admit that it might still allow someone to recover both the masked value of that key piece and the mask value itself. so it’s not a complete fix for every scenario.
Priya: That means we still have to be careful; we get protection against this specific attack, but there are other ways an attacker could try to get around that masking later on.
Nadia: They flagged that limitation, and they showed their improved functions base mul2 and base mul3 were still resistant to the SPA attack when they tested them over ten million calls.
Elias: Their conclusion is basically that implementing these new multiplication routines offers a way to compute faster while staying protected from this specific side-channel method of extracting key material.
Priya: It’s interesting because it shows that hardening cryptography isn't just about changing the math, but also about making sure the low-level code and how it handles those calculations is also robust against physical leakage.
Nadia: Right; so these new functions are a practical step for developers trying to secure their post-quantum implementations without totally sacrificing performance. we’ll look next at what else is going on in the world of AI security because this paper shows how physical implementation leaks can be just as damaging as the math itself.
Conclusion: Tom: So we’re wrapping up this look at "Simple Power Analysis of Polynomial Multiplication in HQC," which basically shows how you can recover a chunk of the private key from just one power trace during the early decryption steps.
Nadia: Yeah, it really boils down to this: physical implementation details matter just as much as the underlying math when you’re dealing with post-quantum stuff like HQC.
Elias: They did show that these new base mul2 and base mul3 functions offer a performance boost while being resistant to this specific simple power analysis attack.
Priya: So, the main thing we see is that you can get this speed improvement without just relying on abstract theoretical protections; you need concrete code changes.
Nadia: Exactly; it’s about making the actual polynomial multiplication routine physically harder to analyze using power consumption measurements.
Elias: They also introduced classical masking techniques, like Boolean masking, which is a way to obscure those intermediate private key values during the multiplication steps in HQC decryption.
Priya: I still have that concern that even with these masks, an attacker could potentially recover both the masked value and the mask itself later on.
Nadia: True; they pointed out that there’s still room for refinement in how robust those masking schemes are against more sophisticated side-channel attacks.
Elias: In summary, this paper confirms that focusing on how polynomial multiplication is actually coded is crucial for security in this area because physical leakage can reveal key material.
Priya: It’s a solid piece of research showing the practical side of measurement and exploitation when applied to these new cryptographic standards.
Nadia: And it sets a benchmark for developers needing to be extra careful about the low-level operations in any post-quantum scheme they build.
Elias: We’ll keep an eye on those findings as we look at other HQC implementations out there and see if this pattern holds true elsewhere.
Czech Technical University in Prague
cs.CR
Submitted: 2026-01-12
Updated: 2026-01-12
Comments: Submitted to ICISSP 2026, 12th International Conference on Information Systems Security and Privacy
Journal ref: In Proceedings of the 12th International Conference on Information Systems Security and Privacy - Volume 2: ICISSP, 2026, pp. 299-306
Code: https://github.com/PQClean/PQClean
License: http://creativecommons.org/licenses/by-sa/4.0/
Importance score: 79/100
The gist: The single-trace Simple Power Analysis (SPA) attack against HQC exploits power consumption leakage during polynomial multiplication at the beginning of HQC decryption to recover a significant portion…
Key concepts
- Simple Power Analysis (SPA)
- This attack method analyzes the overall power consumption trace of a cryptographic operation to identify patterns. The researchers looked for distinct power signatures corresponding to specific steps in the polynomial multiplication algorithm, such as those related to key bits, allowing them to deduce secret information without needing complex statistical analysis.
- Hamming Quasi-Cyclic (HQC)
- HQC is a specific type of lattice-based public-key cryptosystem. The paper focuses on its decryption process because the power consumption leakage occurs during the initial polynomial multiplication step, which is crucial for recovering the private key from encrypted data.
- Polynomial Multiplication (Karatsuba/mul1)
- The core mathematical operation targeted is multiplying two polynomials using a recursive Karatsuba algorithm, specifically implemented via the mul1 algorithm. The power consumption during this specific multiplication step leaks information about the private key polynomial 'y' being processed.
Terminology
Summary
The single-trace Simple Power Analysis (SPA) attack against HQC exploits power consumption leakage during polynomial multiplication at the beginning of HQC decryption to recover a significant portion of the private key
Attack Target and Context
The paper presents a single-trace simple power analysis (SPA) attack against the Hamming Quasi-Cyclic (HQC) cryptosystem which exploits power consumption leakage that occurs during polynomial multiplication performed at the beginning of HQC decryption. The goal of this attack is to recover the private key by analyzing power consumption during polynomial multiplication that is performed at the beginning of HQC decryption. p. 0 In this paper, we present a single-trace simple power analysis (SPA) attack against HQC. The aim of our
attack is to recover the private key by analyzing power consumption during polynomial multiplication that
is performed at the beginning of HQC decryption. The aim of our
attack is to recover the private key by analyzing power consumption during polynomial multiplication that
is performed at the beginning of HQC decryption. The target implementation of our attack is the Additional
implementation of HQC included in the NIST Round 4 submission (Melchor et al. The target implementation of our attack is the Additional
implementation of HQC included in the NIST Round 4 submission (Melchor et al. The target implementation is particularly relevant as it is included in the PQClean library (PQClean,
2025), which is a collection of clean implementations of post-quantum cryptographic algorithms, and is
also in the liboqs library (Open Quantum Safe project, 2025), a C library developed as part of the Open
Quantum Safe project that aims to develop and integrate quantum-safe cryptography into applications.Where the paper says it
Where the paper says it
Where the paper says it
Multiplication Algorithm Vulnerability
The attack focuses on recovering the value of the private key polynomial y by targeting the polynomial multiplication u · y. The target of the attack is a polynomial multiplication implemented using a recursive Karatsuba algorithm. p. 2 We selected this implementation because it is included in both the PQClean (PQClean, 2025) and
liboqs (Open Quantum Safe project, 2025) libraries, as noted in the introduction. The target of our attack is a polynomial multiplication implemented using a recursive Karatsuba algorithm. 1 Multiplication Algorithm
The implementation of the multiplication algorithm is shown in Listing 1. The implementation is based on
the mul1 algorithm presented in the paper Faster multiplication in GF(2)[x] (Brent et al. In the target
implementation of HQC, the value stored in a serves as the private key. Therefore, the objective of our
attack is to recover a by analyzing power consumption.Where the paper says it
Where the paper says it
Where the paper says it
Attack Setup and Methodology
To carry out the simple power analysis attack successfully, the authors use the ChipWhisperer-Lite board which consists of a 32-bit Arm Cortex-M4 based microcontroller (STM32F303) as the target. The attack involves measuring power consumption traces and identifying peaks within the cropped trace using the find peaks function from the Python library SciPy. p. 4 To obtain these two figures, we first captured a single power consumption trace, then cropped it and
identified peaks within the cropped trace using the find_peaks function from the Python library SciPy. After cropping the trace and identifying the peaks, we can observe that at a certain point in the traces,
there is a noticeable drop between two neighboring peaks. After cropping the trace and identifying the peaks, we can observe that at a certain point in the traces,
there is a noticeable drop between two neighboring peaks. By counting the number of peaks from the
left up to this drop, we obtain the value that the corresponding four bits had during the execution of the
multiplication.Where the paper says it
Where the paper says it
Evaluation and Countermeasures
The overall success rate of the attack was 99.69% over 10 000 attack attempts. p. 0 Using the
ChipWhisperer-Lite board, we perform and evaluate the attack, achieving a 99. 69% success rate over
10 000 attack attempts. It shows that all errors originate
from the first four bits of a, and more specifically, only when the correct values were 0 or 15. The results of our attack evaluation demonstrate the feasibility of recovering a 64-bit portion of the
private key from a single power trace.Where the paper says it
Where the paper says it
-
Reducing the size of the lookup table to one by simply using b itself. p. 7
Where the paper says it
The first approach to defending against the attack presented in this work is to reduce the size of the lookup table to one. In other words, instead of using a lookup table that stores multiples of b, we can simply use b itself.
-
Removing the original countermeasure against cache timing attacks and implementing alternative countermeasures like classical masking technique (Boolean masking). p. 8
Where the paper says it
1 Masking While the implementation shown in Listing 3 is not vulnerable to the SPA attack presented in this work, it may still be vulnerable to cache timing attacks, as well as other power analysis attacks. A possible approach to protecting against these threats is the classical masking technique (Mangard et al.
Performance Analysis of Defenses
The execution times for the functions base mul, base mul2, and base mul3 were measured over 10 000 000 calls. The results indicate that base mul2 was approximately 2. p. 8 434326 s 0. 472569 s
As shown in Table 1, the function base_mul2 is approximately 2. 472569 s
As shown in Table 1, the function base_mul2 is approximately 2. 3× faster than base_mul, while
base_mul3 is approximately 6. 1 Multiplication Algorithm
The implementation of the multiplication algorithm is shown in Listing 1. The implementation is based on
the mul1 algorithm presented in the paper Faster multiplication in GF(2)[x] (Brent et al. We also implemented two new multiplication functions, base_mul2 and base_mul3, which are protected against the proposed SPA attack. After implementing these functions, we evaluated their performance
and found that they are not only resistant to our attack but also offer a significant performance advantage. 1 a = a ^ mask ;
2 uint64_t c [2];
3 base_mul (c ,a ,b);
4
5 uint64_t unmask [2];
6 base_mul ( unmask , mask ,b);
7
8 c [0] = c [0] ^ unmask [0];
9 c [1] = c [1] ^ unmask [1];
Listing 4: Implementation of masking designed to protect the value of a against cache timing attacks and
power analysis attacks. It is important to note that, while this masking technique is effective, an attacker may still be able to
carry out successful attacks on the two performed multiplications and potentially recover the masked value
of a and the mask value.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
In this paper, a new single-trace simple power analysis (SPA) attack against HQC is proposed which recovers a significant portion of the private key. The attack was performed 10 000 times with a 99. p. 4 These inputs are used by the script to crop the power consumption trace and determine
the values of all 16 sets of four bits of a, as explained in Section 5. To evaluate the attack, we performed it 10 000 times with random values of a and b. Using the
ChipWhisperer-Lite board, we perform and evaluate the attack, achieving a 99. 69% success rate over
10 000 attack attempts. We also implemented two new multiplication functions, base_mul2 and base_mul3, which are protected against the proposed SPA attack. After implementing these functions, we evaluated their performance
and found that they are not only resistant to our attack but also offer a significant performance advantage. 9× faster. In future work, we plan to further analyze other implementations of HQC and assess their resistance
against side-channel attacks.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
REFERENCES
velekpav, tomas.rabas, jiri. p. 0 Simple Power Analysis of Polynomial Multiplication in HQC
Pavel Velek , Tomáš Rabas , and Jiˇrí Bucek ˇ
{velekpav, tomas. rabas, jiri. Simple Power Analysis of Polynomial Multiplication in HQC
Pavel Velek , Tomáš Rabas , and Jiˇrí Bucek ˇ
{velekpav, tomas. rabas, jiri. Simple Power Analysis of Polynomial Multiplication in HQC
Pavel Velek , Tomáš Rabas , and Jiˇrí Bucek ˇ
{velekpav, tomas. rabas, jiri. Simple Power Analysis of Polynomial Multiplication in HQC
Pavel Velek , Tomáš Rabas , and Jiˇrí Bucek ˇ
{velekpav, tomas. rabas, jiri. Simple Power Analysis of Polynomial Multiplication in HQC
Pavel Velek , Tomáš Rabas , and Jiˇrí Bucek ˇ
{velekpav, tomas. rabas, jiri.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
velekpav, tomas.rabas, jiri.bucek@fit.cvut.cz 2
velekpav, tomas.rabas, jiri.bucek@fit cvut@pg1
velekpav, tomas rabas jiri bucek@fit cvut. p. 0 rabas, jiri. bucek}@fit. rabas, jiri. bucek}@fit. rabas, jiri. bucek}@fit. rabas, jiri. bucek}@fit. rabas, jiri. bucek}@fit.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
velekpav, tomas.rabas, jiri.bucek@fit cvut@pg4
velekpav, tomas.rabas, jiri.bucek@fit cvut@pg5
velekpav, tomas.rabas jiri bucek@fit cvut.cz 6
velekpav, tomas.rabas jiri bucek@fit cvut.cz 7
velekpav, tomas.rabas jiri bucek@fit cvut.cz 8
velekpav, tomas.rabas jiri bucek@fit cvut.cz 9
velekpav, tomas.rabas jiri bucek@fit cvut.cz 10
velekpav, tomas.rabas, jiri bucek@fit cvut. p. 0 rabas, jiri. bucek}@fit. rabas, jiri. bucek}@fit.Where the paper says it
Where the paper says it
velekpav, tomas.rabas, jiri bucek@fit cvut.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved detection of private key information during HQC decryption by analyzing power consumption during polynomial multiplication that is performed at the beginning of HQC decryption, specifically targeting a 64-bit portion of the private key. The improved system can recover a significant part of the secret key through single-trace Simple Power Analysis (SPA) attacks against HQC implementations.
-
Development of new multiplication functions, base mul2 and base mul3, that are protected against the proposed SPA attack while maintaining high performance advantages over the original implementation. These improved functions allow for faster polynomial multiplication in post-quantum cryptographic operations without introducing timing vulnerabilities exploitable by side-channel attacks.
-
Implementation of a classical masking technique, specifically Boolean masking, to protect private key values during polynomial multiplication steps in HQC decryption. This allows the system to compute intermediate results while obscuring the actual values being processed from power analysis attacks, though further refinement is needed to mitigate potential recovery of masked values and masks.
Abstract
The Hamming Quasi-Cyclic (HQC) cryptosystem was selected for standardization in the fourth round of the NIST Post-Quantum Cryptography (PQC) standardization project. The goal of the PQC project is to standardize one or more quantum-resistant public-key cryptographic algorithms. In this paper, we present a single-trace Simple Power Analysis (SPA) attack against HQC that exploits power consumption leakage that occurs during polynomial multiplication performed at the beginning of HQC decryption. Using the ChipWhisperer-Lite board, we perform and evaluate the attack, achieving a 99.69% success rate over 10 000 attack attempts. We also propose various countermeasures against the attack and evaluate their time complexity.
Related papers
- From Strategy Search to Policy Learning: MCTS-Guided Adversarial Co-Evolution for LLM Safety Alignment
- Privacy Leakage from Recurrent State in LLM Inference
- Incrementally Verifiable Oracle Aided Computation
- Privilege and confidentiality in generative AI workflows
- BadMoE: Backdooring Mixture-of-Experts LLMs via Routing-Aware Triggers and Task-Underutilized Experts
- CoVault: Secure, Scalable Analytics of Personal Data