How is the security of NTRUEncrypt measured?
The hard problem underlying the NTRUEncrypt Public Key Cryptosystem is that of finding a very short vector in a lattice of very high dimension. The best way known to attack NTRUEncrypt is to use the LLL lattice reduction method to search for the target vector. In order to test the security of NTRUEncrypt, we used LLL to run numerous tests on NTRUEncrypt lattices of various dimensions and graphed the amount of time it took to find the target vector. From this graph we extrapolated the running time for lattices of higher dimension and used these figures to select appropriate parameters for NTRUEncrypt. The following table gives estimated breaking times for NTRUEncrypt and RSA at various security levels. (Times are rounded to the nearest 10 MIPS-years.
