# Single Trace Analysis on Constant Time CDT Sampler and Its Countermeasure
## 4 Proposed Countermeasure
### Table-Based CDT Sampler  
Note that the output of the CDT sampler is determined from the moment the random value is selected from the uniform distribution. Let \(\Psi[i]=\{26,64,90,103\}\) be the corresponding CDT as in Section 2. The CDT sampler outputs 0 when the random value selected is between [0, 26] and outputs 1 when the random value selected is between [26, 64] and so on. Thus, we can make the look-up table as follows:  
From the above table, we can construct the CDF table as \(\Phi[i]=\{0,\ldots,0,1,\ldots 1,2,\ldots,4\}\). A similar method was implemented in ([PERSON] et al., 2018), where the look-up table was constructed from the start and end addresses of the linear feedback shift register. Sampling values from this reconstructed CDF table are as denoted in Algorithm 3.  
Unlike the constant-time CDT sampler described in Algorithm 2, the execution of Algorithm 3 does not depend on the sampled random value. In Algorithm 2, whether the selected random value is greater than the CDT table value was visible in the power consumption trace due to the difference in Hamming weight of positive and negative values. This vulnerability is eliminated in our countermeasure by precalculating what output of the sampler will be given the random input value. As soon as a random value is selected (step 2 of Algorithm 3) Algorithm 3 uses the random value as the index of the table \(\Phi\) and outputs the corresponding table value. Since there is no Hamming weight difference or the difference in the execution of an algorithm depending on the selected random value, an attacker cannot extract information from a single power consumption trace.  
```
0: CDF look-up table \(\Phi,\sigma,\tau\)
0: Sampled value \(S\)
1:\(sign\leftarrow[0,1]\cap\mathbb{Z}\) uniformly at random
2:\(rnd\leftarrow[0,\tau\sigma)\cap\mathbb{Z}\) uniformly at random
3: return \(S\leftarrow(-sign)\wedge\Phi[rnd]+sign\)
```  
**Algorithm 3** STA-resistant CDT sampling  
However, Algorithm 3 exposes the sign bit through STA in the same manner as in Algorithm 2. In order to prevent the exposure of the signed bit, one can additionally sample one more bit from the uniform distribution and double the length of the table instead of sampling the sign bit separately. For example, suppose that the original algorithm selects eight bits uniformly at random, where the first seven bits correspond to a uniform random integer in [0, 128] and the last bit is used to determine the sign of the sampled value. To use the look-up table for sampling, first, sample 8 bits, and map to integer [0, 128] when the most significant bit is 0 and to \((-128,0]\) when the least significant bit is 1. Then, Table 1 changes to Table 2 with the length doubled.  
One disadvantage of this algorithm is that it needs to store a look-up table. However, since the output of the Gaussian sampler does not exceed one byte, for \(\lambda\)-bit of precision, we need a table size of \(2^{\lambda}\) bytes for Table 1 and \(2^{\lambda+1}\) bytes when using Table 2. When applying the look-up table method to lattice-based cryptosystem, table size is approximately 128-1024 bytes for Table 1 and 256-2048 bytes for Table 2. Specifically, for FrodoKEM-640, since the CDT sampler uses a 7-bit random value, the size of Table 1 is 128 bytes, and the size of Table 2 is 256 bytes. Considering the Knuth-Yao table (1080 bytes for LOTUS-128 that aims the brute-force security of AES-128 [29]) used in the lattice-based cryptosystem, we believe that this storage size is acceptable.