Quantum and Post Quantum Cryptography

Abstract

Public key cryptography is widely used for signing contracts, electronic voting, encryption, and to secure transactions over the Internet. The discovery by Peter Shor, in 1994, of an efficient algorithm based on quantum mechanics for factoring large integers and computing discrete logarithms undermined the security assumptions upon which currently used public key cryptographic algorithms are based, like RSA, El Gamal and ECC. However, some cryptosystems, called post quantum cryptosystems, while not currently in widespread use are believed to be resistant to quantum computing based attacks. In this paper, we provide a survey of quantum and post quantum cryptography. We review the principle of a quatum computer as well as Shor’s algorithm and quantum key distribution. Then, we review some cryptosystems undermined by Shor’s algorithm as well as some post quantum cryptosystems, that are believed to resist classical and quantum computers.