Paper 2022/1740

A Holistic Approach Towards Side-Channel Secure Fixed-Weight Polynomial Sampling

Markus Krausz, Ruhr University Bochum
Georg Land, Ruhr University Bochum, German Research Centre for Artificial Intelligence
Jan Richter-Brockmann, Ruhr University Bochum
Tim Güneysu, Ruhr University Bochum, German Research Centre for Artificial Intelligence

The sampling of polynomials with fixed weight is a procedure required by round-4 Key Encapsulation Mechanisms (KEMs) for Post-Quantum Cryptography (PQC) standardization (BIKE, HQC, McEliece) as well as NTRU, Streamlined NTRU Prime, and NTRU LPRrime. Recent attacks have shown in this context that side-channel leakage of sampling methods can be exploited for key recoveries. While countermeasures regarding such timing attacks have already been presented, still, there is no comprehensive work covering solutions that are also secure against power side channels. To close this gap, the contribution of this work is threefold: First, we analyze requirements for the different use cases of fixed weight sampling. Second, we demonstrate how all known sampling methods can be implemented securely against timing and power/EM side channels and propose performance-enhancing modifications. Furthermore, we propose a new, comparison-based methodology that outperforms existing methods in the masked setting for the three round-4 KEMs BIKE, HQC, and McEliece. Third, we present bitsliced and arbitrary-order masked soft- ware implementations and benchmarked them for all relevant cryptographic schemes to be able to infer recommendations for each use case. Additionally, we provide a hardware implementation of our new method as a case study and analyze the feasibility of implementing the other approaches in hardware.

Available format(s)
Publication info
Published elsewhere. PKC 2023
PQCMaskingCortex-M4FPGAFixed Weight SamplingSide-Channel Countermeasures
Contact author(s)
markus krausz @ rub de
georg land @ rub de
jan richter-brockmann @ rub de
tim gueneysu @ rub de
2023-03-08: revised
2022-12-19: received
See all versions
Short URL
No rights reserved


      author = {Markus Krausz and Georg Land and Jan Richter-Brockmann and Tim Güneysu},
      title = {A Holistic Approach Towards Side-Channel Secure Fixed-Weight Polynomial Sampling},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1740},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.