Is NTRU vulnerable to attacks based on quantum computing?
There is no known quantum computing algorithm which speeds up attacks on NTRU. In general, there are two quantum computing algorithms of great significance to cryptanalysis: Shor’s algorithm and Grover’s algorithm. Shor’s algorithm uses the fact that quantum computing methods can calculate the period of a periodic function very quickly. This can be used to massively speed up attacks on RSA, Discrete Log based cryptosystems such as DSA and Diffie-Hellman, and Elliptic Curve Discrete Log systems such as ECDSA, ECMQV, and so on. (Note that in the case of RSA the period of the function essentially is the private key). Shor’s algorithm has no obvious application to NTRU: NTRU has no similar periodic function to exploit. Grover’s algorithm speeds up unsorted database and brute force searches: using Grover’s algorithm, it is possible to search a list of N items in sqrt(N) time. This effectively halves the keylength of symmetric ciphers. However, there is no obvious application to NTRU, as in
