# Cold Boot Attacks on the Supersingular Isogeny Key Encapsulation (SIKE) Mechanism
## 5 Evaluation of Our Key-Recovery Algorithm
### Integrating a Quantum Key Search Algorithm with Our Key-Recovery Approach  
Throughout this subsection we give a detailed account of a quantum key enumeration algorithm, denoted as QKEA [42], and show how to combine it with our key-recovery algorithm to improve its overall performance. We additionally derive the running time of step 5 of our key recovery algorithm (worst case) if QKEA is run. Recall that at step 5, the lists \(L_{\texttt{B}^{j}}\), for \(0\leq j<n_{b}\), will be given as parameters to an instance of the quantum key enumeration algorithm (QKEA). QKEA relies on a non-optimal key enumeration algorithm developed from a rank algorithm (also known as a counting algorithm) by [PERSON] et al. [17]. The core idea is to leverage the rank algorithm to return a single candidate key with a particular rank within a specific range. Additionally, we remark that this algorithm uses a map that associates each score with a weight (a positive integer), where the smallest weight is regarded as the likeliest one [17]. We assume the scores from each block candidate in the list \(L_{\texttt{B}^{j}}\), for \(0\leq j<n_{b}\), are mapped to weights, as shown in [27; 42]. Given the range \([B_{1},B_{2})\), the rank algorithm constructs a two dimensional array B with \(n_{b}\times B_{2}\) entries, and then uses it to compute the number of full key candidates in the range. Algorithm 6 constructs the two dimensional array B and its running time is given by  
\[T_{1}(n_{b},M,B_{2}) =c_{1}+\sum_{b=0}^{B_{2}-1}\sum_{j=0}^{M-1}c_{2}+\sum_{i=0}^{n_{b }-2}\sum_{b=0}^{B_{2}-1}\sum_{j=0}^{M-1}c_{3}\] \[=c_{1}+c_{2}\cdot M\cdot B_{2}+c_{3}\cdot M\cdot(n_{b}-1)\cdot B_ {2}\]  
where \(M_{j}=M\in\{256,512,1024\}\) for \(0\leq j\leq n_{b}-1\), \(n_{b}\in\{7,8\}\) and \(c_{1}\), \(c_{2}\), \(c_{3}\) are constants, i.e., upper bounds on the running time consumed by primitive operations, such as return operations, addition operations, comparison operations. ```
1:functioncreate(\(B_{1},B_{2}\))
2:\(i\gets n_{b}-1\) ;
3:\(\texttt{B}\leftarrow\left[\left[0\right]^{B_{2}}\right]^{n_{b}}\)
4:for\(b=0\) to \(B_{2}-1\)do
5:for\(j=0\) to \(M-1\)do
6:if\(B_{1}-b\leq c_{j}^{i}score<B_{2}-b\)then
7:\(\texttt{B}_{i,b}\leftarrow\texttt{B}_{i,b}+1\)
8:endif
9:endfor
10:endfor
11:for\(i=n_{b}-2\) to \(0\)do
12:for\(b=0\) to \(B_{2}-1\)do
13:for\(j=0\) to \(M-1\)do
14:if\(b+c_{j}^{i}score<B_{2}\)then
15:\(\texttt{B}_{i,b}\leftarrow\texttt{B}_{i,b}+\texttt{B}_{i+1,\texttt{B}+c_{j}^{i} score}\) ;
16:endif
17:endfor
18:endfor
19:endfor
20:return B;
21:endfunction
```  
**Algorithm 6** constructs the two dimensional array B. Note that, by construction, \(\texttt{B}_{0,0}\) is the number of full key candidates of which total scores are in the interval \([B_{1},B_{2})\). So the rank algorithm simply returns \(\texttt{B}_{0,0}\) and is described by Algorithm 7. Concerning its running time, it is given by \(T_{2}(n_{b},M,B_{2})=c_{4}+T_{1}(n_{b},M,B_{2})\), where \(c_{4}\) is a constant, i.e., an upper bound on the running time of primitive operations. ```
1:functionrank(\(B_{1},B_{2}\))
2:\(\texttt{B}\leftarrow\texttt{create}(B_{1},B_{2})\);
3:return\(\texttt{B}_{0,0}\)
4:endfunction
```  
**Algorithm 7** computes the number of full key candidates in \([B_{1},B_{2})\). By using Algorithms 7 and 8 returns the full key candidate with rank \(r\) in the given range \([B_{1},B_{2})\)[42]. We remark that Algorithm 8 is deterministic and that the full key candidate returned by it is not necessarily the \(r^{th}\) highest-scoring full key candidate in the given range. Regarding Algorithm 8's running time, it is given by  
\[T_{3}(n_{b},M) =c_{5}+\sum_{i=0}^{n_{b}-2}\sum_{j=0}^{M-1}c_{6}+\sum_{j=0}^{M-1 }c_{7}\] \[=c_{5}+c_{6}\cdot M\cdot(n_{b}-1)+c_{7}\cdot M\]  
where \(c_{5}\), \(c_{6}\), \(c_{7}\) are constants, i.e., upper bounds on the running time consumed by primitive operations.