## 4 Key Recovery
### Key Recovery Algorithm  
In this section we present our key recovery strategy, which is an adaptation of a general key recovery strategy introduced in [5]. Using the notation outlined in Section 2.3.5, let \(\mathtt{ns}=(b_{0},\ldots,b_{W-1})\) denote the bits of the noisy encoding of the private seed and let us name the chunks \(\mathtt{ns}^{0},\mathtt{ns}^{1},\ldots\mathtt{ns}^{N-1}\) so that \(\mathtt{ns}^{i}=b_{i:w}b_{i:w+1}\ldots b_{i:w+(w-1)}\), where \(\mathcal{N}=W/w\). In our setting, we set \(W=256\) bits and \(w=8\), i.e., each chunk is a byte, and thus \(\mathcal{N}=32\). Furthermore, we partition ns into \(n_{\mathtt{B}}\) blocks, where each block consists of the concatenation of \(n_{\mathtt{B}}^{j}\), with \(n_{\mathtt{B}}^{j}>0\), consecutive chunks, such that \(\mathcal{N}=\sum_{j=0}^{n_{\mathtt{B}}-1}n_{\mathtt{B}}^{j}\). Therefore,  
\[\mathtt{ns}=\mathtt{B}^{0}||\mathtt{B}^{1}||\mathtt{B}^{2}||\cdots\mathtt{B}^ {n_{\mathtt{B}}-1}\]where  
\[\mathtt{B}^{j}=\mathtt{ns}^{i_{j}}||\mathtt{ns}^{i_{j}+1}||\ldots||\mathtt{ns}^{ i_{j}+n_{b}^{j}-1}\]  
for \(0\leq j<n_{\mathtt{B}}\) and some \(0\leq ij<\mathcal{N}\). We now proceed with Phase I as follows. 1. For each chunk \(\mathtt{ns}^{i}\), with \(0\leq i<\mathcal{N}\), we use Equation (1) to compute a log-likelihood score for each candidate \(\mathtt{c}^{i}\) for the chunk \(\mathtt{ns}^{i}\). Hence, lists containing up to \(2^{w}\) chunk candidates, \(L_{\mathtt{ns}^{i}}\), may be produced. In our case, the candidates are the \(2^{8}\) possible values, hence each list is of size \(256\). 2. For each block \(\mathtt{B}^{j}\), the lists \(L_{\mathtt{ms}^{i_{j}}},L_{\mathtt{ms}^{j+1}},\ldots,L_{\mathtt{ns}^{j+n_{b}^ {j}-1}}\) are passed as inputs to an instance of an optimal key enumeration algorithm (denoted as OKEA), in order to create a list containing the \(M_{j}\) candidates having the highest scores for the block \(\mathtt{B}^{j}\), \(L_{\mathtt{B}^{j}}\). Regarding OKEA used in this phase, it is introduced in [24] and enumerates complete candidates \(\mathtt{c}\) in a decreasing order based on their scores. Expressed in a different way, it first generates the complete candidate that has the highest score, then the one having the second highest score and so on. Therefore, it allows us to find the top \(M_{j}\) candidates with the highest scores in decreasing order, where \(1\leq M_{j}\ll 2^{W}\). In our setting, \(M_{j}\) is chosen to be the same value for each block and may take a value in the set \(\{256,512,1024\}\). Once Phase I is completed, we proceed with Phase II as follows. 1. The lists \(L_{\mathtt{B}^{j}}\) are passed as inputs to an instance of a key enumeration algorithm, which considers each list \(L_{\mathtt{B}^{j}}\) as a set of candidates for the block \(\mathtt{B}^{j}\). This instance will generate candidates with a high score for the encoding of the key. Each candidate \(\mathtt{c}\) generated by the enumeration algorithm is presented as input to a verification function \(V\) to determine whether such complete candidate may be regarded as valid or not. As a verification function, we adapt the LUOV key generation algorithm, as shown in Algorithm 2. Note that \(\mathtt{s}\) is a \(32-\)byte array that represents a full key candidate generated by the Phase II key enumeration algorithm, while \((\mathtt{public\_seed,Q_{2}})\) is a byte array that represents the public key (without noise). Additionally, note that this test is expected to run very quickly, since the condition of the first \(\mathtt{if}\) is very likely to be \(\mathtt{true}\) only when the enumeration has found the real private seed, since \(\mathcal{H}\) is a collision resistant cryptographic hash function. In other words, only the first two instructions (evaluations of \(\mathcal{H}\)) plus a few instructions of the comparison Arrays.equal(\(\mathtt{public\_s,public\_seed}\)) will likely be executed for almost all complete candidates generated by the key enumeration algorithm.