1 Introduction
Invented in 1970s, Public-Key Cryptography (PKC) made it possible to establish a shared key between two parties communicating over a public channel without using a prior shared secret. Since then, PKC research has resulted in Public-Key Encryption (PKE), key agreement and digital signature schemes. The most widely used PKC algorithms are the RSA and Elliptic Curve Cryptography (ECC). The security of these two cryptosystems relies on the hardness of the integer factorization and discrete logarithm problems respectively. These problems are presumed to be computationally infeasible to solve using traditional computers. However, Shor’s algorithm [1] can solve these problems in polynomial time and thus break the RSA and ECC efficiently using a large-scale quantum computer. Rapid advancement in quantum computing in recent years have made the development of small-scale quantum computers possible [2]. Many scientists anticipate that large-scale quantum computers able to break RSA and ECC will be feasible within the next 20 years [3]. If such quantum computers are ever built, they will completely destroy the present-day public-key infrastructure. Hence, we need next-generation PKC algorithms that cannot be broken by quantum computers.