International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Markus Krausz , Ruhr University Bochum
Georg Land , Ruhr University Bochum
Jan Richter-Brockmann , Ruhr University Bochum
Tim Güneysu , Ruhr University Bochum and DFKI Bremen
DOI: 10.1007/978-3-031-31371-4_4
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
Abstract: 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 software 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.
  title={A Holistic Approach Towards Side-Channel Secure Fixed-Weight Polynomial Sampling},
  author={Markus Krausz and Georg Land and Jan Richter-Brockmann and Tim Güneysu},