# Single Trace Analysis on Constant Time CDT Sampler and Its Countermeasure
## 1 Introduction
Recently, security against side-channel attacks on a Gaussian sampler has been recognized as an important problem. Just as side-channel analysis has been thoroughly performed on classical cryptosystems such as RSA or ECC, we also need to examine the case in lattice-based cryptography. A side-channel attack proposed by [PERSON] et al. in 1996 is an attack based on exploiting information gained from the physical implementation of a cryptographic system [9]. In order to substitute RSA or ECC with post-quantum cryptography, resistance against side-channel analysis is required. Hence, researchers are examining possible side-channel attacks on lattice-based cryptography. Particularly, side-channel attacks on Gaussian sampling have been proposed [7; 10; 11]. Since the Gaussian sampler uses different random values each time of execution, side-channel attacks that exploit multiple iterations of an algorithm such as differential power analysis (DPA) cannot be performed. Moreover, since efficiency is as important as security when implementing the Gaussian sampler, countermeasures that significantly degrade the performance cannot be used. In this regard, current implementation on Gaussian samplers mainly considers timing attacks so that constant-time algorithms on Gaussian sampling have been proposed [7; 12; 13; 14]. However, single-trace attacks targeting the Gaussian sampler have not been analyzed so far. The goal of this work is to examine the vulnerability of the current implementation of CDT sampler and to provide its countermeasure. Due to its efficiency, the CDT sampler is one of the most widely used algorithms. As stated above, a constant-time CDT sampler is implemented to withstand timing side-channel attacks. The following list details the main contributions of this work. * We performed the first single trace analysis (STA) on a constant-time CDT sampler. We theoretically and experimentally analyzed that existing a constant-time CDT algorithm is vulnerable to STA. Our attack is simple as it does not have any restriction on the attack environment. We exploit the gap of Hamming weight between the positive and negative value to recover the sampled value through a single power consumption trace. When the errors are known, the attacker can reveal the secret key by solving \(As=B-e\). Therefore, every lattice-based cryptosystem including key exchange is vulnerable to STA. Details of our attack are presented in Section 3. * We proposed an efficient countermeasure based on look-up table schemes. Especially for the Gaussian sampling algorithm used in lattice-based cryptography, the countermeasures must be as efficient as possible since every entry of an error matrix used in the cryptosystem requires executions of the sampler individually. In this regard, at least 2000 samplings are required for single executions of an algorithm proposed nowadays. Our countermeasure is efficient since it is faster than the constant-time CDT sampler, with the use of ROM. However, the additional memory usage is minimal--only about 256 to 2048 bytes, depending on the choice of parameter. To validate the efficiency of our countermeasure, we implemented it in FrodoKEM and Lizard and compared its speed. * We present an implementation result to validate the efficiency of our proposed countermeasure. We implemented our countermeasure in Lizard, one of the submitted candidates in NIST standardization projects [15]. From our result, we demonstrated that our countermeasure does not degrade the performance of the constant-time CDT sampler. The result of our implementation is given in Section 4. This paper is organized as follows: Section 2 recalls the definition of a lattice and describes lattice-based cryptography and a CDT sampler. In Section 3, our attack on constant-time CDT sampler is described. We propose our countermeasure in Section 4 and conclude in Section 5.