BKW-attack on NTRUCIPHER and NTRUCIPHER+ encryption schemes

Authors

  • Alexandra Matiyko Institute of special communication and information protection of National technical university of Ukraine “Igor Sikorsky Kyiv polytechnic institute”, Kyiv, http://orcid.org/0000-0002-6947-5958

DOI:

https://doi.org/10.20535/2411-1031.2020.8.2.222599

Keywords:

postquantum cryptography, lattice-based cryptography, NTRUCipher, NTRUCipher , BKW-attack, Fourier transform

Abstract

Due to the appearance of quantum computers, which will significantly reduce the time of solving certain problems, the security of many standardized cryptosystems is under threat. This prompted NIST to launch an open competition to create new post-quantum standards in 2016. In the summer of 2020, the NTRU algorithm, one of the fastest post-quantum algorithms based on lattices in Euclidean space (1996), was entered the seven finalists of this competition. However, only in 2017 was proposed an analog of this encryption scheme – symmetric encryption scheme NTRUCipher. Preliminary researches of this encryption scheme have been conducted but it’s security to chosen-plaintext attack, which consists of compiling a system of linear equations corrupted by noise (over a finite field of simple order) and solving it using a generalized BKW algorithm, have not been analyzed. For the first time, the NTRUCipher + cipher scheme is proposed in this article. Its main difference is the usage of an additional random polynomial when encrypting. The security of NTRUCipher cipher scheme and its modification NTRUCipher+ against BKW-attack is researched. Such an attack is possible for symmetric NTRU-like cipher schemes but it has not been considered before. Analytical (upper and lower) bounds of the BKW attack’s complexity on NTRUCipher and NTRUCipher + are obtained. The comparison of these cipher schemes on the encrypted messages’ length against BKW-attack at certain identical fixed parameters is carried out. It is shown that the security increase of the NTRUCipher cipher scheme against BKW-attack due to the usage of an additional additive in encryption is almost completely leveled by increasing the upper bound of the decryption failure probability. Research allows to compare these cipher schemes in terms of security and practicality and to conclude that it is inexpedient to use NTRUCipher+ to increase the security of the NTRUCipher cipher scheme to BKW attack. In the future, it is planned to develop methods for constructing symmetric analogs of the NTRU cryptosystem based on other general lattice-based structures.

Author Biography

Alexandra Matiyko, Institute of special communication and information protection of National technical university of Ukraine “Igor Sikorsky Kyiv polytechnic institute”, Kyiv,

lecturer at the state information
resources academic department

References

J. Hoffstein, J. Pipher, and J. Silverman, “NTRU: a new high speed public key cryptosystem”. [Online]. Available: https://web.securityinnovation.com/hubfs/files/ntru-orig.pdf. Accessed on: Sept. 07, 2020.

American national standards institute. (2010, Oct. 15; reafiirmed 2017, Febr. 2). ANSI X9.98-2010. Lattice-based polynomial public key encryption algorithm for the Financial Services Industry. [Online]. Available: https://webstore.ansi.org/preview-pages/ASCX9/preview_ANSI+ X9.98-2010+(R2017).pdf. Accessed on: Sept. 07, 2020.

R. Steinfeld, “NTRU cryptosystem: recent developments and emerging mathematical problems in finite polynomial rings”, Algebraic Curves and Finite Fields: Cryptography and Other Applications, pp. 179-211, 2014, doi: https://doi.org/10.1515/9783110317916.179.

D. J. Bernstein, Ch. Chuengsatiansup, T. Lange, and Ch. van Vredendaal, “NTRU Prime: reducing attack surface at low cost”, in Proc. International Conference on Selected Areas in Cryptography, Ottawa, 2017, pp. 235-260, doi: https://doi.org/10.1007/978-3-319-72565-9_12.

P. Hirschhorn, J. Hoffstein, N. Howgrave-Graham, and W. Whyte, “Choosing NTRU parameters in light of combined lattice reduction and MITM approaches”, Applied Cryptography and Network Security, vol. 5536, pp. 437-455, 2009, doi: https://doi.org/10.1007/978-3-642-01957-9_27.

D. Stehle', and R. Steinfeld, “Making NTRU as secure as worst-case problems over ideal lattices”, in Proc. International Conference on Advances in Cryptology, Tallin, 2011, pp. 27-47, doi: https://doi.org/10.1007/978-3-642-20465-4_4.

M. R. Valluri, “NTRUCipher-lattice based secret key encryption”, in World Congress on Internet Security. [Online]. Available: https://arxiv.org/abs/1710.01928. Accessed on: Sept. 07, 2020.

A. Blum, A. Kalai, and H. Wasserman, “Noise-tolerant learning, the parity problem, and the statistical query model”, Journal of the ACM, vol. 50, no. 3, pp. 506-519, 2003, doi: https://doi.org/10.1145/792538.792543.

A. N. Alekseychuk, S. M. Ignatenko, and M. V. Poremskyi, “Systems of linear equations corrupted by noise over arbitrary finite rings,” Mathematical and Computer Modelling, Series: Technical science, iss. 15, pp. 150-155, 2017, doi: https://doi.org/10.32626/ 2308-5916.2017-15.150-155.

M. R. Albrecht at al., “Estimate all the {LWE, NTRU} schemes!”, in Proc. International Conference on Security and Cryptography for Networks, Amalfi, 2018, pp. 351-367, doi: https://doi.org/10.1007/978-3-319-98113-0_19.

S. Diop, D. O. Sane', M. Seck, and N. Diarra, “NTRU-LPR IND-CPA: a new ideal lattice-based scheme”, Cryptology ePrint Archive, Report 2018/109. [Online]. Available: http://eprint.iacr.org/2018/109. Accessed on: Sept. 07, 2020, doi: 10.13140/RG.2.2.15424. 35840.

A. A. Matiyko, “The comparative analysis of NTRUCipher and NTRUEncrypt encryption schemes”, Mathimatical and computer modelling. Series: Technical science, iss. 19, pp. 81-87, 2019, doi: https://doi.org/10.32626/2308-5916.2019-19.81-87.

А. N. Alekseychuk, А. А. Matiyko, “Estimates of the probability of reversibility of random polynomials used in the modified version of NTRU cryptosystem”, Radiotekhnica, iss. 189, pp. 38-46.

L. Babai, “The Fourier transform and equations over finite abelian groups”. [Online]. Available: http://people.cs.uchicago.edu/~laci /ren/fourier.pdf. Accessed on: Sept. 07, 2020.

Published

2020-12-30

How to Cite

Matiyko, A. (2020). BKW-attack on NTRUCIPHER and NTRUCIPHER+ encryption schemes. Information Technology and Security, 8(2), 164–176. https://doi.org/10.20535/2411-1031.2020.8.2.222599

Issue

Section

CRYPTOLOGY