# Post-Quantum Migration of the Tor Application
## 2 Literature Review
### Schemes
#### 2.2.1 Key Exchange
This work ignores strong cryptosystems such as McEliece, which imposes a substantial key size and, therefore, communication overhead. The current cell size limit remains an obstacle to the hybrid or full PQC migration for all layers. Concerning the relay layer, no key exchange has been processed, but the challenge also concerns signature schemes. Regarding the link layer, it produces key exchange within its TLS implementation. RFC [37] standard defines the handshake with three core stages: server parameters, key exchange, and authentication. In a PQC environment, the second phase would rely on KEMs. The third is reviewed in the next section. Currently, Tor's TLS \begin{table}
\begin{tabular}{l c c c c c} \hline \hline  & **Keygen/s** & **Keygen** & **Encaps/s** & **Decaps/s** & **Security** \\  & **(Cycles)** & **Encaps/s** & **Decaps/s** & **Category** \\ \hline HQC-128 & 6719.33 & 371,892 & 3571.00 & 2349.00 & 1 \\ HQC-192 & 2855.00 & 875,523 & 1465.00 & 1000.00 & 3 \\ Kyber512 & 23,348.00 & 106,974 & 18,970.00 & 16,118.00 & 1 \\ Kyber768 & 13,660.67 & 182,899 & 11,630.00 & 10,096.33 & 3 \\ sntrup761 & 115.55 & 21,636,049 & 2308.00 & 818.00 & 2 \\ FrodoKEM-640-SHAKE & 345.99 & 7,224,951 & 282.67 & 280.33 & 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: KEM performance comparison. Operations per second per algorithm, reference code type (unoptimised), 2024-04-02, OQS [35]. \begin{table}
\begin{tabular}{l c c c} \hline \hline  & **Encapsulation Key** & **Ciphertext** & **Secret Key** \\ \hline HQC-128 & 2249 & 4487 & 56 \\ HQC-192 & 4522 & 9042 & 64 \\ HQC-256 & 7245 & 14,485 & 72 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Sizes (in bytes) of keys and ciphertexts of HQC [36]. uses P256 ECDHE (and still has legacy support for secp224r1) for handshakes and Ed25519 for server identity, known as link keys [10]. Indeed, ML-KEM-768 appears to be the selected parameter for the newly adopted designs [22]. [PERSON] [38], in a fork of [PERSON], experimented with the integration of hybrid key exchange TLS with X25519 Kyber768 Draft00. In 2020, [PERSON] et al. [39] presented the performance trade-offs of several schemes, including hybrid ECDH-P256-Kyber512. Compared to the classical p-256 curve, the hybrid scheme shows an increase in packet loss and completion time. Their work highlights the effect of higher RTTs, where the hybrid scheme demonstrates greater degradation; in their conclusion, the authors discussed how the enlargement of the MTU might improve TLS establishment performance. In 2024, the post-quantum TLS survey by [PERSON] et al. [40] points out the significant impact of large keys, using FrodoKEM as an analogy. FrodoKEM takes 2.7\(\times\) the time of a Kyber handshake and 2.53\(\times\) the time of a typical classical handshake with \(\times\)25519. They state that the combination of Kyber512 (NIST security level 1) and \(\times\)25519 took 1.25\(\times\) the time of a traditional handshake, while NIST level 3 of this hybridisation has a very close performance (1.28\(\times\)). Finally, the paper provides an overview of how the work of [19] differs from other designs in its approach of achieving AKE as the pure PQC solution KEMTLS. Indeed, KEMTLS is achieving a form of 1W-AKE, as the server is authenticated to the client without DSA by using a long-term KEM public key for encapsulation, with the server responding via an encapsulation based on the client's ephemeral KEM public key. Therefore, achieving a 1W-AKE means the client does not need to authenticate itself. A pure KEM 1W-AKE implementation is interesting in the context of the future circuit-extension handshake. Recently, [PERSON] and al. [41] introduced a one-way Verifiable Weak FS notion and presented the first lattice-based tightly FS AKE via key confirmation in the classical random oracle model (using the lattice-based protocol from [PERSON] et al. [42]), showing that the OW-VwFS can be transformed _tightly_ to FS using key confirmation in the random oracle model (ROM).