Study on NTRU Decryption Failures
Weichi Yu, David He, Shixiong Zhu · 2005
NTRU [1, 2, etc] is a new public key encryption scheme based on hard problems in lattice. Due to the linear operations, both encryption and decryption of NTRU are very fast [2]. However, decryption of this scheme may be failed even for recommended parameters. In this paper, NTRU decryption failures are analyzed. As a result, the theoretical bound of parameters is presented, which guaranteed NTRU decryption failure free. In order to correct NTRU decryption failures, we designed a compensating algorithm. To our knowledge, this algorithm is better than any other ones for NTRU decryption failure correction. An example is given at the end of this paper.