International Association
for Cryptologic Research

In this work, we examine widespread components of various Post-Quantum Cryptography (PQC) schemes that exhibit disproportionately high overhead when implemented in software in a side-channel secure manner: fixed-weight polynomial sampling, Cumulative Distribution Table (CDT) sampling, and rotation of polynomials by a secret offset. These components are deployed in a range of lattice-based and code-based Key Encapsulation Mechanisms (KEMs) and signature schemes from NIST’s fourth round of PQC standardization and the signature on-ramp. Masking – to defend against power Side-Channel Analysis (SCA) – on top of required constant-time methods, leads in some of these cases to impractical runtimes. To solve this issue, we start by identifying a small set of core operations, which are crucial for the performance of all three components. We accelerate these operations with an Instruction Set Extension (ISE) featuring masked instructions, which are generic and low-level and can be used in a wide range of cryptographic applications and thereby tackle performance, microarchitectural power leakage, and cryptographic agility, simultaneously. We implement dedicated masked instructions for our core operations as an add-on to the RISC-V core by Gao et al. which features masked instructions for Boolean and arithmetic operations and evaluate several algorithmic approaches in standard and bitsliced implementations on different ISE constellations. Our instructions allow some masked components to run more than one order of magnitude faster and are first-order power side-channel secure, which our practical evaluation confirms.