# Secure Cryptographic Key Encapsulation and Recovery Scheme in Noisy Network Conditions
## 5 Key Encapsulation and Recovery Method Using CRP  
In this protocol, the initial step involves the generation of a key with a length of N Bits with a random number generator (RNG). This key is called an ephemeral key (K). To encapsulate this key, we use a CRP mechanism that generates a set of N P-bit long responses from N Challenges. One example of a protocol is where the N challenges are generated from an RNG; they point at a memory array programmed with randomly selected zeros and ones to generate the N responses or one of the examples mentioned in Example of CRP Generation for Noise-Tolerant Cryptographic Protocols. A subset of responses is generated from the set of N responses by keeping only the positions in K where the bit value is 1 and discarding the positions with a bit value of 0. On average, this results in N/2 responses. An example of the protocol of interest is to introduce noise into the system by randomly flipping \(T\) out of \(P\) bits with the responses of the subset. \(T\) has to be kept within an acceptable threshold. This noisy subset, along with the cipher text of any secret message that was generated using K as the key, is transmitted over the communication channel, which can also increase the noise level. See Algorithm 1. ```
1:\(K\leftarrow\text{RNG}(N)\)\(\triangleright\) Generate \(N\)-bit ephemeral key \(K\)
2:\(C=\{c_{1},c_{2},\ldots,c_{n}\}\)
3:\(R=\{r_{1},r_{2},\ldots,r_{n}\}\)
4:\(S\leftarrow\{r_{i}\mid K_{i}=1\}\)
5:for\(r_{i}\) in \(S\)do
6:\(r_{i}^{\prime}\leftarrow\text{FlipBits}(r_{i},T)\)
7:endfor
8:Transmit \(\{S^{\prime},\text{Enc}_{K}(\text{message})\}\)
```  
**Algorithm 1** R-KEM Key Encapsulation  
Upon receiving the transmitted data, the receiver reconstructs the set of N responses with the same CRP mechanism and initiates the search process. To recover K, the receiver compares the received subset with the complete set of responses. For each response of the subset, a match is considered successful when only one match is found within the search window (\(\gamma\)); in such a case, the receiver identifies and saves the position as 1. However, if multiple matches are detected, a collision is indicated; all the positions that matched are stored for later analysis and error-correcting schemes. Conversely, if no match is found within the window, a failure to detect is indicated, and all corresponding positions are marked for the error-correcting schemes. The full algorithm is explained in Algorithms 2 and 3. ```
1:Input: Subset of responses \(\{r_{1}^{\prime},\ldots,r_{j^{\prime}},\ldots,r_{s}\}\), full set of responses \(\{r_{1},\ldots,r_{i_{1}},\ldots,r_{N}\}\), \(\gamma_{0}\) and threshold \(T\)
2:Initialize \(j=1\), \(i=1\), and \(\gamma=\gamma_{0}\)
3:Initialize lists: NoMatches[], OneMatch[], Collisions[]
4:while\(i<N+1\)do
5: Compute Hamming distance \(H(r_{j}^{\prime},r_{i+k})\) for all \(r_{i+k}\) with \(k\in\{0,\gamma-1\}\)
6:if\(H(r_{j}^{\prime},r_{i+k})>T\) for all \(k\)then
7:for all \(k\)do
8: Append \(i+k\) to NoMatches[]
9:endfor
10: Increment \(i\) and \(j\) by \(1\); set \(\gamma=2\gamma_{0}-1\)
11:elseif\(H(r_{j}^{\prime},r_{i+k})\leq T\) for exactly one \(k\)then
12: Append \(i+k\) to OneMatch[]
13: Increment \(j\) by \(1\), \(i=i+k+1\), set \(\gamma=2\gamma_{0}\)
14:else
15: Find the smallest and largest \(k\) values where \(H(r_{j}^{\prime},r_{i+k})\leq T\)
16:for all \(k\) values found do
17: Append \(i+k\) to Collisions[]
18:endfor
19: Increment \(j\) by \(1\); set \(i=i+k_{min}+1\); set \(\gamma=\gamma_{0}+(k_{max}-k_{min})\)
20:endif
21:endwhile
22:Output: NoMatches[], OneMatch[], Collisions[]
```  
**Algorithm 2** R-KEM Error Detection  
Throughout the search process, the receiver accumulates information regarding the positions that resulted in matches, as well as those that had collisions or failures to detect. The matched positions are retained as a \"\(1\)\", whereas the positions associated with collisions or failures are used to discover the correct key.