  In this work, we propose a study on the use of post-quantum cryptographic
primitives for the Tor network in order to make it safe in a quantum world.
With this aim, the underlying keying material has first been analysed. We
observe that breaking the security of the algorithms/protocols that use long-
and medium-term keys (usually RSA keys) have the highest impact in security.
Therefore, we investigate the cost of quantum-safe variants. These include key
generation, key encapsulation and decapsulation. Six different post-quantum
cryptographic algorithms that ensure level 1 NIST security are evaluated. We
further target the Tor circuit creation operation and evaluate the overhead of
the post-quantum variant. This comparative study is performed through a
reference implementation based on SweetOnions that simulates Tor with slight
simplifications. We show that a quantum-safe Tor circuit creation is possible
and suggest two versions - one that can be used in a purely quantum-safe
setting, and one that can be used in a hybrid setting.
