# Single Trace Analysis on Constant Time CDT Sampler and Its Countermeasure
## 2 Preliminaries
### Discrete Gaussian Sampling  
Before describing the Gaussian sampling algorithms, the discrete Gaussian distribution on a lattice is defined below. **Definition 7**. : _(Discrete Gaussian Distribution) Let \(L\subset\mathbb{Z}^{n},c\in\mathbb{R}^{n},\sigma\in\mathbb{R}^{+}\). Define:_  
\[\rho_{\sigma,c}(x)=exp\big{(}-\pi\frac{||x-c||^{2}}{\sigma^{2}}\big{)}\text{ and }\rho_{\sigma,c}(L)=\sum_{x\in L}\rho_{\sigma,c}(x).\]  
_The discrete Gaussian distribution over lattice \(L\) with center \(c\) and parameter \(\sigma\) is defined as_  
\[\forall x\in L,D_{L,\sigma,c}(x)=\frac{\rho_{\sigma,c}(x)}{\rho_{\sigma,c}(L)}.\]  
_For \(c=0\), denote \(\rho_{\sigma,0}\) as \(\rho_{\sigma}\) and \(D_{L,\sigma,0}\) as \(D_{L,\sigma}\)._  
In lattice-based cryptography, one has to sample a vector from a discrete Gaussian distribution on a lattice \(L\subset\mathbb{Z}^{n}\). This reduces to sampling \(n\) number of integers from a discrete Gaussian distribution on \(\mathbb{Z}\). There are several methods for sampling numbers from Gaussian distributions. Gaussian sampling algorithms aim to produce a distribution of random numbers that are statistically close to the ideal Gaussian distribution within a certain bound, depending on the security parameter. The distance between the two distributions can be measured by statistical distance. The statistical distance between the distribution generated by Gaussian sampler \(X\) and ideal Gaussian distribution \(Y\) is defined as follows:  
\[\Delta(X,Y)=\frac{1}{2}\sum_{x\in L}|Pr(X=x)-Pr(Y=x)|.\]  
Given the security parameter \(\lambda\), we aim to produce random numbers from \(X\) with certain precision so that its statistical distance between ideal Gaussian distribution \(Y\) is \(\Delta(X,Y)<2^{\lambda}\). Recently, [PERSON] et al. proposed that Renyi divergence can be used as an alternative to the statistical distance in security proofs for lattice-based cryptography [8]. The definition of Renyi divergence is as follows. **Definition 8**. : _(Renyi divergence of order a) For any two discrete probability distribution \(P\) and \(Q\), where \(Supp(P)\subseteq Supp(Q)\), and \(a\in(0,\infty)\), Renyi divergence of order \(a\) is defined as_  
\[R_{a}(P\|Q)=\left(\sum_{x\in Supp(P)}\frac{P(x)^{a}}{Q(x)^{a-1}}\right)^{\frac {1}{x-1}}.\]  
[PERSON] et al. showed that using Renyi divergence in place of statistical distance can result in less precision in the implementation of the security analysis for lattice-based cryptography [8]. In some cases, using Renyi divergence leads to security proofs allowing for taking smaller parameters in the cryptographic schemes. For more information, please refer to [8]. The work of [PERSON] et al. is evidence that Gaussian sampling is an integral part of lattice-based cryptography that affects both security and efficiency. In [13], [PERSON] and [PERSON] also stated that the discrete Gaussian sampling can be the main hurdle in implementation, and a bottleneck to achieve good performance. For example, one parameter set of FrodoKEM-640 requires \(640\times 8=5,120\) entries in the error matrix, which is equal to the number of samplings needed [18]. Therefore, one has to consider the characteristics of an algorithm and a minimum number of bits required to satisfy the desired security level for efficient implementation. Before presenting the Gaussian sampling methods used in this field, the parameters needed in Gaussian sampling are as follows [19]. * **The standard deviation:** The standard deviation \(\sigma\) determines the shape of the Gaussian distribution. The larger the standard deviation, the more difficult the implementation. That is, the required bits and table sizes increase when the standard deviation is large. * **The precision parameter:** The precision parameter \(\lambda\) determines how close the Gaussian sampler is to the ideal Gaussian distribution. * **The tailcut parameter:** Given a target security of \(\lambda\) bits, the target distance from the ideal Gaussian distribution should not be no less than \(2^{\lambda}\).