Logical Mistakes in NTRU Compensation Algorithm and Improvement of Encryption Verification Algorithm

The basic security of NTRU is based on the hardness of the shortest vector problem (SVP) of some lattice, named as CS lattice. Dealing with the decryption failure problem of NTRU is an important topic. The logical mistakes and defects of NTRU compensation algorithm which is used for dealing with the decryption failure problem of NTRU are analyzed. The compensation algorithm is proven to be incorrect in this paper. It seems that NTRU encryption verification algorithm can cope with the decryption failure problem of NTRU. But in fact, it is hard to get a satisfying result. An improvement scheme on NTRU encryption verification algorithm is also put forward and discussed, which can correctly resume the plaintext in high probability while the security is the same with NTRU.