Why is NTRUEncrypt resistant to parallelized attacks?
The hard problem underlying the NTRUEncrypt cryptosystem is that of finding short vectors in lattices of high dimension. To solve this problem, one uses lattice reduction methods, more specifically the Lenstra-Lenstra-Lovasz (LLL) algorithm with various improvements due to Schnorr, Euchner, Horner, and others. In a similar manner, people use the number field sieve (NFS) to factor integers and break RSA, and they use the Pollard rho method (PRM) to find elliptic curve discrete logarithms and break ECC. One way to make these methods (LLL, NFS, PRM) faster is to simultaneously use a large number of computers. In order to understand how this is done, we need to distinguish between two different ways that computers can interact: Parallelized Computation If many computers are permanently connected so that they can perform computations while continuously communicating with one another, then they able to perform parallel computations. Note that it is possible to have a single computer box that
