BKW-attack on NTRUCIPHER and NTRUCIPHER+ encryption schemes
DOI:
https://doi.org/10.20535/2411-1031.2020.8.2.222599Keywords:
postquantum cryptography, lattice-based cryptography, NTRUCipher, NTRUCipher , BKW-attack, Fourier transformAbstract
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.
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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 Information Technology and Security
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors that are published in this collection, agree to the following terms:
- The authors reserve the right to authorship of their work and pass the collection right of first publication this work is licensed under the Creative Commons Attribution License, which allows others to freely distribute the published work with the obligatory reference to the authors of the original work and the first publication of the work in this collection.
- The authors have the right to conclude an agreement on exclusive distribution of the work in the form in which it was published this anthology (for example, to place the work in a digital repository institution or to publish in the structure of the monograph), provided that references to the first publication of the work in this collection.
- Policy of the journal allows and encourages the placement of authors on the Internet (for example, in storage facilities or on personal web sites) the manuscript of the work, prior to the submission of the manuscript to the editor, and during its editorial processing, as it contributes to productive scientific discussion and positive effect on the efficiency and dynamics of citations of published work (see The Effect of Open Access).
