Identification of influential parameters for NTRU decryption failure and recommendation of extended parameter selection criteria for elimination of decryption failure

• Main Authors: Gaithuru, J. N., Salleh, M., Bakhtiari, M.
• Format: Article
• Language: English
• Published: International Association of Engineers 2017
• Subjects: QA75 Electronic computers. Computer science
• Online Access: http://eprints.utm.my/id/eprint/76218/1/MazleenaSalleh_IdentificationofInfluentialParametersforNTRU.pdf; http://eprints.utm.my/id/eprint/76218/; https://www.scopus.com/inward/record.uri?eid=2-s2.0-85028080166&partnerID=40&md5=57f253038af6f4a37b87c770f0a4a1b1

NTRU is the leading alternative to ECC and RSA in the post-quantum era. However, it has a probability of decryption failure of 2-k (with k being the security level) according to Philip S. Hirschhorn, Jeffrey Hoffstein, Nick Howgrave-Graham and William Whyte, 2009. This probability was provided for parameters selected using an algorithm which provides security against lattice reduction and MITM attacks, with particular emphasis on parameter size and coefficients of the private key. The recommendations for selection of polynomials in NTRU described by Hoffstein, Jeff Howgrave-Graham, Nick Pipher, Jill Whyte and William in 2010 prescribed that for polynomial f of binary form. In this paper, we re-evaluate the prescribed parameter selection criteria by rigorous testing of different polynomial combinations of f, g, m and φ as well as q for varied security levels. The testing experimentally verifies the influential parameters for NTRU operation whose results are used to propose an extended correlated parameter selection criteria for the private key, which ensures that a randomly selected polynomial f is invertible and that an accurate selection of the minimum size of q required for successful decryption is made.