Cipher Analysis Of NTRU

With the rapid development of quantum computing,most public key cryptosystem,such as RSA,ECC etc.,can be broken within polynomial time complexity by quantum computer algorithm.NTRU has drawn considerable attention for its potential antiquantum ability,high speed,low memory requirements.In this thesis,we focus on the security of NTRU cryptosystem under the classical attack and lattice attack.The main achievements are as follows.1)Based on the combination of multiple transmission attack and broadcast attack,a new broadcast attack against NTRU is proposed.We proved the practicality of the new attack by theoretical analysis and experimental verification.In this new attack,two methods are used to obtain more information about plaintext and reduce the number of channels used in a whole attack.First,”pseudo-collisions” between random polynomials are used to decrease the possible number of values the random polynomial's coefficients may achieved.Second,guessing the rest unknown coefficients of a random polynomial is also a good trick.We then reduced the number of channels and unknowns.2)A new lattice called IN-lattice is constructed by intersecting of some low-dimensional lattices.The IN-lattice has lower dimension and better property compared with the classical NTRU-lattice.We then proposed an efficient new lattice attack against NTRU.The new attack has lower requirements on the strength of the lattice reduction algorithm by the Root-Hermite-Factor analysis.The correct choice of corresponding parameters of the new attack is proved by a large number of experiments.