Paper 2024/114

X2X: Low-Randomness and High-Throughput A2B and B2A Conversions for $d+1$ shares in Hardware

Abstract

The conversion between arithmetic and Boolean masking representations (A2B \& B2A) is a crucial component for side-channel resistant implementations of lattice-based (post-quantum) cryptography. In this paper, we first propose novel $d$-order algorithms for the secure addition (SecADDChain$_q$) and B2A (B2X2A). Our secure adder is well-suited for repeated ('chained') executions, achieved through an improved method for repeated masked modular reduction. The optimized B2X2A gadget removes a full secure addition compared to state-of-the-art B2A approaches, by relying on the X2B operation. This component directly converts a compositely shared variable, consisting of a mix of arithmetic and Boolean sharing, to $d+1$ Boolean shares. This approach reduces the required amount of SecADDs to $2d$, of which $2\cdot\lceil\text{log}_2(d)\rceil$ are max-order. Secondly, we develop both a first- and high-order masked, unified hardware implementation that can compute both A2B & B2A conversions for power-of-two ($p$) and prime ($q$) moduli. Compared to state-of-the-art (high-throughput) hardware implementations that only support A2B$_k$, we reduce area utilization for a second-order implementation by 45% up to 60% and fresh randomness up to 62%, while supporting all four types of additive mask conversions. Our first-order design only requires 1,133/2,170 [LUT/FF] on Kintex-7 FPGAs. Our proposed algorithms are proven secure in the robust probing model and their implementations are validated via practical lab analysis using the TVLA methodology. We experimentally show that our masked implementation is hardened against first-and second order univariate and multivariate power-based side-channel attacks using 100 million traces, for each mode of operation.