# 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
```
1:functiongetKey(B,\(B_{1},B_{2},r\))
2:if\(r>\texttt{B}_{0,0}\)then
3:return\(\bot\)
4:endif
5:\(\texttt{k}\leftarrow[0]^{n_{b}}\);
6:\(b\gets 0\);
7:for\(i=0\) to \(n_{b}-2\)do
8:for\(j=0\) to \(M-1\)do
9:if\(r\leq\texttt{B}_{i+1,b+c_{j}^{i},score}\)then
10:\(\texttt{k}_{i}\gets j\);
11:\(b\gets b+c_{j}^{i}\);\(score\);
12:break\(j\);
13:endif
14:\(r\gets r-\texttt{B}_{i+1,b+c_{j}^{i},score}\);
15:endfor
16:endfor
17:\(i\gets n_{b}-1\);
18:for\(j=0\) to \(M-1\)do
19:\(x\leftarrow\left(B_{1}-b\leq c_{j}^{i}score<B_{2}-b\right)?1:0\);
20:if\(r\leq x\)then
21:\(\texttt{k}_{i}\gets j\);
22:break\(j\);
23:endif
24:\(r\gets r-x\);
25:endfor
26:return\(\texttt{k}\)
27:endfunction
```  
**Algorithm 8** returns the \(r^{th}\) full key candidate with weight in the interval \([B_{1},B_{2})\). By calling the getKey function, Algorithm 9 tries to enumerate and test all full key candidates in the given interval [42]. Note that Test is pointer to the testing function (Algorithm 5). Concerning Algorithm 9's running time, it is given by \(T_{4}(n_{b},M,B_{2},e)=c_{8}+T_{1}(n_{b},M,B_{2})+e\cdot(T_{3}(n_{b},M)+c_{9}+T (\texttt{Params}))\), where \(e\) is the number of full key candidates in the range \([B_{1},B_{2})\), \(c_{8}\) and \(c_{9}\) are constants and upper bounds on the running time consumed by primitive operations, and \(T(\texttt{Params})\) is the running time of the testing function (Algorithm 5). ```
1:functionkeySearch(\(B_{1},B_{2},\texttt{Test}\))
2:\(\texttt{B}\leftarrow\texttt{create}(B_{1},B_{2})\);
3:\(r\gets 1\);
4:whileTruedo
5:\(\texttt{k}\leftarrow\texttt{getKey}(B,B_{1},B_{2},r)\);
6:if\(\texttt{k}=\bot\)then
7:break;
8:endif
9:ifTest(\(\texttt{k})=1\)then
10:break;
11:endif
12:\(r\gets r+1\);
13:endwhile
14:return\(\texttt{k}\);
15:endfunction
```  
**Algorithm 9** enumerates and tests all full key candidates with weight in the interval \([B_{1},B_{2})\). Algorithm 10 calls the function keySearch to search over partitions selected independently with approximately \(a^{s}\) full key candidates for \(s=0,1,\ldots\)[42]. Regarding Algorithm 10's running time, this is given by  
\[T_{5}(n_{b},m,B_{e},B_{2},e,a)=c_{10}+\log_{2}(e)\cdot T_{2}(n_{b},M,B_{e})+ \sum_{s=0}^{p-1}(T_{4}(n_{b},M,B_{2},a^{s})+\log_{2}(a^{s})\cdot T_{2}(n_{b},M,B_{2})-1) \tag{6}\]  
where \(p=\log_{a}(e\cdot(a-1)+1)\) and \(e\in\{2^{30},2^{40},2^{50}\},c_{10},c_{11}\) are upper bounds on the running time consumed by primitive operations, such as return operations, addition operations, comparison operations. The terms \(\log_{2}(e)\cdot T_{2}(n_{b},M,B_{e})\) and \(\log_{2}(a^{s})\cdot T_{2}(n_{b},M,B_{2})\) are the running times of steps 5 and 13 of Algorithm 10. Note that this algorithm is similar to NOKEA in the sense that it also enumerates full key candidates of which total scores belongs to the given range. Furthermore, the technique of partitioning the entire interval helps in improving the overall performance of Algorithm 10 when it is searching over an initial range with a large number of full key candidates. Given the computational burden of Algorithm 10 lies on the execution of the function keySearch (at step 7), then any improvement on this search algorithm implies a speed-up on Algorithm 10's overall performance. The authors of [42] show how this part may be modified by replacing it for a Grover's oracle [43], and so improving Algorithm 10's overall performance. Algorithm 11 results from adjusting Algorithm 10 and relies on a Grover's oracle, giving a quadratic speed-up on searches over partitions. The function \(\texttt{f}(r)=\texttt{Test}(\texttt{getKey}(\texttt{B},B_{1},B_{2},r))\) returns 1, on the condition that \(r\) is the rank of the real secret key; otherwise, it returns 0. [PERSON]'s algorithm [43] shows that \(r\) can be found on a quantum computer in only \(\mathcal{O}\Big{(}\Big{|}a^{s/2}\Big{|}\cdot T_{f}\Big{)}\) steps, where \(T_{f}\) is the time to evaluate \(\texttt{f}(r)\), i.e., \(T(\texttt{Params})+T_{3}(n_{b},M)\).