The world is facing an increasing threat from quantum computers. All widely deployed public key cryptosystems, namely, RSA, ECC and (EC)DH, will be broken due to Shor’s algorithm running on a quantum computer. To mitigate this threat, NIST started a call for proposal to identify cryptographic algorithms that are secure against quantum computers (a.k.a, post-quantum cryptosystems or PQC).
Modern technology is all about buzz words. Unless you have been trapped in the phantom zone for the past few years, you must have heard of quantum computers and blockchains. Some say that quantum computers are the next generation of computers, and blockchains are the next generation of the Internet. What will the next generation look like when we have both quantum computers and blockchains in a same room? A quantum apocalypse.
NTRU is a cryptosystem that uses a special type of polynomial ring. The underlying hardness assumption, known as the NTRU assumption, is that an inverse of a short polynomial (polynomial whose coefficients are very short compared to the modulus q) is indistinguishable from a uniformly random polynomial in this ring. This indistinguishability is crucial in designing a cryptosystem.