Bounds of decryption failure probability in NTRUEncrypt encryption scheme for a fixed key

Abstract

The asymmetric encryption scheme NTRUEncrypt is one of the fastest post-quantum encryption schemes. To date, there are several versions of this encryption scheme but all of them have an unwanted feature that assumes decryption failure. Besides the inconvenience for authorized users, this feature leads to specific attacks on the encryption scheme and consequently reduces its security. The traditional approach to estimating the decryption failure probability assumes that this probability is determined by random selection of all elements used to form the encrypted message: the plain text, the key and so-called randomizing polynomial. At the same time, from a practical point of view, a more adequate indicator of the failure frequency is the set of probabilities calculated for each fixed value of the secret key. In this article, we get upper bounds for the decryption failure probability for a fixed key for one of the most extensive versions of the NTRUEncrypt encryption scheme. The first of two obtained bounds is approximate in the sense that, when it is proved, the replacement of the probability distribution of certain independent random variables sum by the limit (normal) distribution is carried out. The second obtained bound is due to Hoeffding's inequality and it is not based on any heuristic assumptions. In general, the obtained results provide more adequate information about the frequency of decryption failure for the considered version of NTRUEncrypt and can be used later in choosing the parameters of this encryption scheme to optimize it for security or practicality.