Post-Quantum Cryptography and Quantum Cloning

Introduction

In cryptography, several public-key cryptosystems are based on hard problems (not easily tractable on classical computers) such as discrete logarithms and integer factorization. Over the years, number of cryptography algorithms have been introduced and played a crucial role in cybersecurity such as Rivest-Shamir-Adleman (RSA) cryptosystem, Diffie-Hellman key exchange, elliptic curve cryptosystems (ECC) and digital signature algorithm (DSA). Nowadays, quantum computing is an exceptionally hot area of research. The era of quantum computing is nearly upon us, and quantum computers will be able to perform certain operations more quickly and efficiently than classical ones. It is based on quantum mechanical principles of superposition and entanglement. Feynman (1982) stated that the simulation of quantum mechanics was performed on a classical computer. Initially, it was thought to be only a theoretical interest, but now the race to develop a truly useful quantum computer is on among major IT companies and research communities.

Shor (1994) developed a polynomial quantum algorithm which can solve the above intractable problems easily on a quantum computer. As the rapid advancement in quantum computers is catching up, Shor’s factorization algorithm will completely end the RSA encryption. It take space complexity and time on a quantum computer and time on a classical computer to find factors of a large number n. Therefore, current popular public-key cryptosystems can be attacked in polynomial time. Bernstein (2009) shown the status of several present public-key cryptosystems, given in Table 1.