Survey on computationally hard problems and their applications to cryptography

Security of several cryptosystems rests on different computational hard problems. Many popular cryptographic schemes are based on the intractability of number theoretic problems such as factoring and discrete logarithms. These hard problems are widely believed to be intractable for classical algorithms. However, these problems may turn to be polynomial-time solvable when the quantum computer comes into existence. Therefore, it is desired to investigate new classes of alternative candidates of hard problems that have exponential complexity to both the ordinary and quantum computers, for instance, error correcting codes, lattice problems, braid groups and subset - product. In this paper, we will focus on the computationally hard problems and their applications to cryptography.