# Single Trace Analysis on Constant Time CDT Sampler and Its Countermeasure
## 2 Preliminaries
### Lattice-Based Cryptography  
Intuitively, a lattice can be defined as a discrete subgroup of \(\mathbb{R}^{n}\) or a set of integer combinations of basis. Below is the formal definition of a lattice. **Definition 1**. : _Let \(B=\{b_{1},...,b_{d}\}\subset\mathbb{Z}^{n}\) be a set of \(d\) independent vectors. Then, the set_  
\[L(\{b_{1},...,b_{d}\})=\left\{\sum_{i=1}^{d}x_{i}\cdot b_{i}|x_{i}\in\mathbb{Z}\right\} \tag{1}\]  
_is a lattice and \(B\) is called a basis of \(L\)._  
Given two bases \(B\) and \(B^{\prime}\), \(B\) and \(B^{\prime}\) generate the same lattice if and only if there exists a unimodular matrix \(U\) such that \(B=UB^{\prime}\). It is known that there are infinitely many bases for a given lattice \(L\), and some bases are considered as \"good\" and many are considered as \"bad\". Using a \"good\" basis, one can solve lattice problems more efficiently. Below are definitions of some of the computational problems on lattices. **Definition 2**. : _(Shortest Vector Problem, SVP) Given an arbitrary basis \(B\) of some lattice \(L=L(B)\), find a shortest nonzero lattice vector._  
**Definition 3**. : _(Closest Vector Problem, CVP) Given an arbitrary basis \(B\) of some lattice \(L=L(B)\), and a target vector \(t\in\mathbb{R}^{n}\), find some \(v\in L\) such that \(||t-v||\leq\gamma\cdot dist(t,L)\), where \(dist(L,t)=min_{x\in L}||x-t||\) and \(\gamma\geq 1\) is an approximation factor._  
The above problems are known to be NP-hard, and several cryptosystems based on these problems have been proposed. Since there is no quantum algorithm to solve these problems efficiently,such lattice-based cryptosystems are secure even against quantum computers. The first public-key cryptosystem based on lattice was proposed by [PERSON] and [PERSON] in 1997 [2]. Although their system was theoretically secure, it was inefficient due to large public-key, private key, and ciphertext sizes. Meanwhile, NTRU was proposed in 1996 by [PERSON], [PERSON], and [PERSON] [16]. Their system was based on the closest vector problem and has remained secure until now. NTRU is famous for faster operation compared with RSA at equivalent cryptographic strength. In 2005, [PERSON] proposed that the LWE problem is as hard to solve as several worst-case lattice problems [3]. He showed a quantum reduction from worst-case lattice problems such as SVP to LWE. This LWE problem can be considered as an extension of the \"learning parity with noise\" problem to higher moduli. [PERSON] further proposed a public-key cryptosystem based on this problem, which is significantly more efficient than the previous lattice-based cryptosystems [3]. The public-key is of size \(\tilde{O}(n^{2})\) and encrypting a message increases its size by a factor of \(\tilde{O}(n)\), where previous cryptosystems were \(\tilde{O}(n^{4})\) and \(\tilde{O}(n^{2})\), respectively. Before describing the LWE problem, we first define the LWE distribution. (LWE distribution) For a vector \(s\in\mathbb{Z}_{q}^{n}\), called the secret, the LWE distribution \(A_{s,X}\) over \(\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}\) is sampled by choosing \(a\in\mathbb{Z}_{q}^{n}\) uniformly at random, choosing \(e\leftarrow\chi\) and generating \((a,b=<s,a>+e\mod q)\). In the above definition, \(\chi\) is an error distribution over \(\mathbb{Z}\), usually taken to be a discrete Gaussian distribution. There are two versions of the LWE problem: the search-LWE problem that aims to find the secret vector given LWE samples and the decision-LWE problem that aims to distinguish between LWE samples and uniformly random samples. Below are definitions of search-LWE and decision-LWE problems [17]. In 2010, [PERSON], [PERSON], and [PERSON] proposed a ring-base analog of LWE problems, known as the ring LWE problem (RLWE) [4]. Due to its structure and the usage of number theoretic transform (NTT) as an underlying computation, RLWE further improved lattice-based cryptography.