Supersingular Isogeny and Ring Learning With Errors-Based Diffie-Hellman Cryptosystems: A Performance and Security Comparison

The purpose of this work is to provide a complexity analysis of the trade-off between performance and security for two post-quantum cryptosystems: isogeny cryptosystems based on supersingular elliptic curves (SSI) and the lattice-based ring learning with errors key exchange (RLWE), considered to be secure against quantum attacks. The intractability of the Computational Supersingular Isogeny Problem (CSSIP) and of the Decisional Supersingular Product Problem (DSSPP) form the basis of the security for cryptosystems based on isogenies between supersingular elliptic curves. As for the RLWE cryptosystem, its security rests on the hardness of the Learning With Errors problem, proven to be as hard as the Shortest Vector Problem (SVP).We analyze the tradeoff between performance and security for both SSI and RLWE cryptosystems in comparison with Discrete Logarithm Problem (DLP) and Integer Factorization Problem (IFP). As complexities increase for the attack algorithms when the key lengths become longer, RLWE outperforms all the other algorithms (including SSI) regarding key sizes at practical security levels.