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

Das Paper "A Holistic Approach Towards Side-Channel Secure Fixed-Weight Polynomial Sampling" von Markus Krausz, Georg Land, Jan Richter-Brockmann und Tim Güneysu wurde für die PKC'23 akzeptiert.


The sampling of polynomials with fixed weight is a procedure required by all remaining 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 that side-channel leakage of sampling methods can be practically 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.
Aiming to close this important gap, the contribution of our 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.

Paper lesen