Lattice based and isogeny based post-quantum cryptography

Modern cryptography involving public-keys relies on mathematically difficult problems, such as factoring large numbers into prime factors and finding rational points on elliptic curves. A typical public-key scheme involves two communicators who each have a public and a private key. Each party publishes their public key so that others may use it to encrypt directed messages while only the individual party uses their private key to decrypt those messages. As computers advance, so too do the methods of breaking cryptographic systems. This drives the development of increasingly difficult cryptographic schemes. While these schemes are more difficult to break and are faster than historic encryption methods, quantum computers threaten the security of classical cryptography. These highly efficient computers will break existing classical ciphers, such as RSA (Rivest Shamir Adleman), ECC (elliptic curve cryptography) and others. It is therefore necessary and urgent to improve cryptographic algorithms to make them resistant to quantum computers. These modifications improve the security of cryptographic schemes and make it more challenging for adversaries to intercept, modify, or decrypt confidential messages. There are currently several areas of research for potential post-quantum cryptographic algorithms. Two such areas are isogeny based cryptography and lattice based cryptography. This kind of cryptography relies on isogenies of elliptic curves as well as lattices and works by each communicating party taking random walks on isogeny graphs. In this report we explain in detail how to find isogenies of elliptic curves, how we can compute isogeny graphs from isogenies of elliptic curves and practical applications of isogeny-based cryptography in the Diffie-Helman key exchange, and lastly analyze the security of the quantum-resistant cryptographic technique. Since this is a new area of research there is no available book which covers in detail all the tools used in isogeny based and lattice based cryptography, so this report is an initiative toward formalization. As quantum computers become more realistic threats to classical cryptography, there is a clear need to develop practical quantum-resistant algorithms. By better understanding and improving cryptographic schemes, our communications in public channels will be better protected from adversaries.