# Post-Quantum Migration of the Tor Application
## 2 Literature Review
### Schemes
#### 2.2.1 Key Exchange
In Table 2, their key and ciphertext sizes are significantly larger compared to the sntrup761 setting except for the shared secret key. Furthermore, ML-KEM presents multiple advantages. It is indistinguishable from a chosen ciphertext attack, assuming that D-MLWE is intractable and that \(G\), \(H\), and \(J\) are random functions. Additionally, it maintains IND-CCA2 by a quantum adversary able to make both classical and quantum queries (in superposition) to \(G\), \(H\), and \(J\)[32; 33]. Above all, it shows encouraging performances in comparison with other schemes [26; 34]. Table 3 shows the three distinct standardised formats of Kyber and their corresponding key sizes. In hybrid implementations, the increase in handshake size tends to lead to higher bandwidth usage and latency during the handshake process. However, the overall performance heavily depends on the underlying mathematical assumption and its implementation. The Open Quantum Safe [35] benchmarking displays the performance of the schemes on x86_64 architecture according to the operations (key generation, encapsulation, decapsulation) per second and per CPU cycle. It ranks HQC-128 and Kyber512, both achieving NIST level 1 security, with higher key generation per second. Table 4 shows a summary of OQS measures for the schemes of interest. Overall, taking into consideration size and performance \begin{table}
\begin{tabular}{l c c c c} \hline \hline  & **Encapsulation Key** & **Decapsulation Key** & **Ciphertext** & **Shared Secret Key** \\ \hline sntrup761 & 1158 & 1763 & 1039 & 32 \\ FrodoKEM-640-AES & 9616 & 19,888 & 9720 & 16 \\ FrodoKEM-640-SHAKE & 9616 & 19,888 & 9720 & 16 \\ FrodoKEM-976-AES & 15,632 & 31,296 & 15,744 & 24 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Sizes (in bytes) of FrodoKEMs and sntrup761’s keys and ciphertexts. \begin{table}
\begin{tabular}{l c c c c} \hline \hline  & **Encapsulation Key** & **Decapsulation Key** & **Ciphertext** & **Shared Secret Key** \\ \hline ML-KEM-512 & 800 & 1632 & 768 & 32 \\ ML-KEM-768 & 1184 & 2400 & 1088 & 32 \\ ML-KEM-1024 & 1568 & 3168 & 1568 & 32 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Sizes (in bytes) of keys and ciphertexts of ML-KEM [33]. attributes, Kyber/ML-KEM appears to be the highest performer. It is followed by HQC, which reaches faster key generation per second and maintains good key encapsulation and decapsulation speeds despite larger key and ciphertext sizes (see Table 5). The streamlined NTRU Prime, sntrup761, comes next with smaller keys and ciphertext sizes than HQC-128, ML-KEM-768, or FrodoKEM-640. Claiming at least the second NIST security category, it represents a trade-off between performance, security, and bandwidth. FrodoKEM tends to fall behind due to reduced operational efficiency, considering its large key sizes and security level. While Kyber is a derivation of the Kyber PKE algorithm using FO transform, HQC uses a variant of the FO transform called HHK, allowing HQC to achieve IND-CCA2 security [36]. Among a few other minor modifications, the FIPS 203 standard for Kyber and ML-KEM specifies a variant of the FO transform for the encapsulation and decapsulation mechanism; in this work, the Kyber benchmarks are considered for evaluating ML-KEM performance. The code-based HQC scheme displays excellent performances, yet its large keys and ciphertexts (Table 5) may require further adaptation to integrate it within Tor protocols. The 512-byte limit affects the amount of data that can be included in the handshake process. The currently open proposal #340 [5] aims to implement a cell packing, optimising cell usage, and a fragmentation mechanism allowing for larger cryptographic keys. Based on the design of proposal #269, the work on PQC migration toward a hybrid handshake [11; 13], and the attributes of the observed schemes, ML-KEM-768 and sntrup761 appear to fit the circuit-extension requirements. HQC may be an alternative if larger keys can be implemented easily.