# Single Trace Analysis on Constant Time CDT Sampler and Its Countermeasure
## 1 Introduction  
The security of currently used public-key cryptosystems is based on the hardness of mathematical problems such as integer factorization or a discrete logarithm problem over a finite field. For example, RSA, proposed in 1977, is based on the hardness of factoring large integers. Elliptic curve cryptography (ECC), proposed in 1985, is based on the hardness of solving discrete logarithm problem on an elliptic curve (ECDLP). Since the currently best-known algorithms for solving integer factorization and ECDLP take sub-exponential time and exponential time, respectively, RSA and ECC are believed to be secure when using large enough parameters. However, due to the seminal work of [PERSON] in 1994, these problems can be solved in polynomial time when a quantum computer is built running the Shor algorithm [1]. For this reason, quantum-resistant cryptographic schemes have become an active area of research due to the increase in concerns over the security of current public-key cryptosystems. Post-quantum cryptography (PQC) refers to cryptographic algorithms executed on a classical computer that is expected to be secure against adversaries with quantum computers. PQC is considered to be secure against quantum computers since there is no known quantum algorithm that can solve security base problems more efficiently than classical algorithms. Five categories are mainly considered in post-quantum cryptography: multivariate-based cryptography, code-based cryptography, lattice-based cryptography, hash-based digital signature, and isogeny-based cryptography. Multivariate-based cryptography is based on the hardness of solving a system of multivariate equations, while code-based cryptography is based on the hardness of decodinggeneral linear code. Lattice-based cryptography is based on the hardness of solving lattice problems and hash-based digital signature is based on the security of cryptographic hash functions. Lastly, isogeny-based cryptography is based on the hardness of finding isogeny between two given elliptic curves. Each cryptosystem in its category has both pros and cons, and no cryptosystem is known to be better than the others. After the National Institute of Standards and Technology (NIST) announced a standardization project for PQC in 2016, its first submission ended in November 2017. Among the 69 submissions, 26 were lattice-based cryptosystems that ranked the highest. Lattice-based cryptography was first proposed by [PERSON] and [PERSON] in 1997 [2]. Later on, due to the groundbreaking work of [PERSON] in 2005 and 2010, lattice-based cryptography became one of the most promising candidates in PQC because of its efficiency [3; 4]. By using the learning with errors (LWE) problem over an ideal lattice as a security base, the key size and ciphertext size have decreased significantly compared with [PERSON] and [PERSON]'s proposal. Therefore, most cryptographic schemes in lattice-based cryptography nowadays are based on the LWE problem. Intuitively, the LWE problem aims to find a solution \(s\) given a sequence of \"approximate\" random linear equations on \(s\). That is, given a set of linear equations on \(s\)--e.g., \(As=B\), where \(A\) and \(B\) are known, we insert an error \(e\) to make the problem significantly more difficult. In this regard, the attacker now needs to solve \(As+e=B\), where \(e\) is unknown to him. Components of this error vectors are selected from a Gaussian distribution. If an attacker knows all the values of error vectors, the system can be easily broken. In this regard, the closer the sampler is to the actual Gaussian distribution, the more secure the cryptosystem is. At the same time, since the Gaussian sampler is one of the main modules in lattice-based cryptography, it must be efficient to avoid performance degradation. Therefore, previous works have been conducted on efficiency and accuracy (i.e., closeness to the ideal Gaussian distribution) trade-off for Gaussian sampling algorithms [5; 6; 7; 8].