Single Trace Analysis of Comparison Operation Based Constant-Time CDT Sampling and Its Countermeasure

Cumulative Distribution Table (CDT) sampling is a Gaussian sampling technique commonly used for extracting secret coefficients or core matrix values in lattice-based Post-Quantum Cryptography (PQC) algorithms like FrodoKEM and FALCON. This paper introduces a novel approach: a single trace analysis (STA) method for comparison operation based constant-time CDT sampling, as employed in SOLMAE—a candidate for Korean Post-Quantum Cryptography (KPQC) first-round digital signature Algorithm. The experiment is measuring power consumption during the execution of SOLMAE’s sampling operation on an 8-bit AVR compiler microcontrollers unit (MCU) using ChipWhisperer-Lite. By utilizing STA, this paper recovered output of comparison operation based constant-time CDT sampling. The source of CDT sampling leakage is investigated through an in-depth analysis of the assembly code. The 8-bit AVR MCU conducts comparison operations on values exceeding 8 bits by dividing them into 8-bit blocks. Consequently, the execution time of a CDT sampling operation is influenced by the outcome of each block’s comparison operation due to conditional branching. To address these concerns, this paper begins by summarizing trends in CDT sampling related research to design robust countermeasures against single trace analysis. Furthermore, a novel implementation method for comparison operation based constant-time CDT sampling against STA is proposed. This assembly-level implementation removes branching statements and performs comparative operations on all data words. Through experimental validation, this paper demonstrates the safety of the proposed countermeasure algorithm against STA.