Method for design secure symmetric NTRU-like encryption schemes
DOI:
https://doi.org/10.20535/2411-1031.2022.10.2.270406Keywords:
post-quantum cryptography, symmetric encryption scheme, NTRUCipher, NTRU Prime, security proofAbstract
Asymmetric NTRU-like encryption schemes are among the fastest modern post-quantum cryptosystems. They are designed on simple (from the point of view of implementation complexity) transformations in truncated polynomials rings and provide required security against well-known attacks if their parameters are properly chosen. The security of such encryption schemes is based on the difficulty of finding short vectors in certain lattices in Euclidean space. Almost a third of all post-quantum cryptographic algorithms submitted to the NIST competition for standardization of post-quantum cryptographic primitives belong to NTRU-like (or close to them as Learning With Errors) cryptosystems. Along with that, an actual task is to create symmetric cryptosystems, the security of which (similarly to asymmetric ones) is based on the complexity of solving only one computationally hard problem. As of now, the only one symmetric NTRU-like encryption scheme is known that is not secure against certain chosen plaintexts attacks – NTRUCipher. The purpose of this article is to develop a method for design symmetric NTRU-like cipher systems that are secure against specified attacks (CPA secure). It is shown that the security of proposed encryption schemes is based on the hardness of the Decision-Ring-LWE problem, which is one of the well-known computationally hard problems in lattice-based cryptography. It is shown that, unlike the previously known NTRUCipher encryption scheme, the proposed encryption schemes are secure against chosen-plaintext attacks. Concurrently, the proposed encryption schemes have the same secret key length as the NTRUCipher encryption scheme. An algorithm for choosing the parameters that ensure the security of proposed encryption schemes at a predetermined level, is presented. It is shown that the time of encryption or decryption messages in proposed encryption schemes is comparable to the corresponding time in the NTRU Prime cryptosystem, which is one of the finalists in the NIST competition of design new post-quantum cryptographic standards.
References
M.R. Albrecht et al., “Estimate all the {LWE, NTRU} schemes!”, in Security and Cryptography for Networks, D. Catalano and R. De Prisco, Eds. Cham, Switzerland: Springer, 2018, vol. 11035, 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, doi: https://doi.org/10.13140/RG.2.2.15424.35840.
V. Lyubashevsky, and G. Seiler, “NTTRU: Truly fast NTRU using NTT”, ACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2019, iss. 3, pp. 180-201, 2019, doi: https://doi.org/10.13154/tches.v2019.i3.180-201.
M.R. Valluri, “NTRUCipher-lattice based secret key encryption”, in Proc. World Congress on Internet Security, Cambridge, 2017, pp. 1-5, doi: https://doi.org/10.48550/arXiv.1710.01928.
А. Matiyko, “BKW-attack on NTRUCIPHER and NTRUCIPHER+ encryption schemes”, Information Technology and Security, vol. 8, iss. 2 (15), pp. 164-176, July – December 2020, doi: https://doi.org/10.20535/2411-1031.2020.8.2.222599.
А. Matiyko, and А. Alekseychuk, “Fast distinguishing attack on NTRUCipher+ encryption scheme”, Ukrainian Information Security Research Journal, vol. 22, no. 3, pp. 183-189, 2020, doi: https://doi.org/10.18372/2410-7840.22.14981.
A. Alekseychuk, and A. Matiyko, “Distinguishing Attack on the NTRUCipher Encryption Scheme”, Cybernetics and Systems Analysis, vol. 58, no. 2, pp. 186-190, 2022, doi: https://doi.org/10.1007/s10559-022-00449-y.
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, 2022.
D. Coppersmith, and A. Shamir, “Lattice attack on NTRU”, in Proc. Advances in Cryptology – EUROCRYPT’97, Konstanz, 1997, pp. 52-61.
D.J. Bernstein, Ch. Chuengsatiansup, T. Lange, and Ch. van Vredendaal, “NTRU Prime: reducing attack surface at low cost”, in Selected Areas in Cryptography – SAC 2017, Ottawa, 2018, pp. 235-260, doi: https://doi.org/10.1007/978-3-319-72565-9_12.
C. Chen, J. Hoffstein, W. Whyte, and Z. Zhang, “NIST PQ Submission: NTRUEncrypt. A lattice based algorithm”, 2017. [Online]. Available: https://csrc.nist.gov/projects/post-quantum-cryptography. Accessed on: Sept. 03, 2022.
J. Katz, and Y. Lindell, Introduction to modern cryptography. Boca Raton, Florida, USA: CRC Press, 2015.
V. Lyubashevsky, “Towards practical lattice-based cryptography”, Doctor of Philosophy in Computer Science University of California, San Diego, CA, USA, 2008. [Online]. Available: https://escholarship.org/uc/item/0141w93p. Accessed on: Aug. 15, 2022.
V. Lybashevsky, C. Peikert, and O. Regev, “On ideal lattices and learning with errors over rings” in Proc. Advanced in Cryptology – EUROCRYPT 2010, French Riviera, 2010, pp.1-23.
S. Ihnatenko, “Security estimates of a Ring-LWE symmetric cryptosystem against chosen plaintext attack”, Cybernetics and Systems Analysis, vol. 58, no. 2, pp. 322-325, 2020, doi: https://doi.org/10.1007/s10559-020-00248-3.
A. Alekseychuk, and M. Poremskyi, “A general scheme for design of correlation attacks on SNOW 2.0-like stream ciphers”, Legal, regulatory and metrological support of information security system in Ukraine, iss. 1 (32), pp. 70-79, 2018.
V. Lyubachevsky, L. Ducas, and E. Kiltz, “CRYSTALS–Delithium. Techn. rep. NIST”, 2017. [Online]. Available: https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-1-submissions. Accessed on: Sept. 12, 2022.
O. Regev, “On lattices, learning with errors, random linear codes, and cryptography” in Proc. the 37th Annual ACM Symposium on Theory of Computing, Baltimore, USA, 2005, pp. 84-93.
A. Alekseychuk, S. Ignatenko, and M. Poremskyi, “Systems of linear equations corrupted by noise over arbitrary finite rings,” Mathematical and Computer Modelling, ser. Technical Sciences, iss. 15, pp. 150-155, 2017, doi: https://doi.org/10.32626/2308-5916.2017-15.150-155.
A. May, “How to Meet Ternary LWE Keys”, in Proc. Advances in Cryptology – CRYPTO 2021. Lecture Notes in Computer Science. Cham, Switzerland: Springer, 2021, vol. 12826, pp. 701-731, doi: https://doi.org/10.1007/978-3-030-84245-1_24.
E. Kirshanova, and A. May, “How to Find Ternary LWE Keys Using Locality Sensitive Hashing”, in Proc. 18th IMA International Conference, IMACC 2021, Virtual Event, Cham, Switzerland: Springer, 2021, vol. 13129, pp. 247-264, doi: https://doi.org/10.1007/978-3-030-92641-0_12.
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.48550/arXiv.cs/0010022.
E. Alkim, L. Ducas, T. Poeppelmann, and P. Schwabe, “Post-quantum key exchange – a new hope”, 2016. [Online]. Available: http://cryptojedi.org/papers/#newhope. Accessed on: Sept. 12, 2022.
J.W. Bos, C. Costello, and L. Ducas, “Frodo: take of the ring! Practical, quantum-secure key exchange from LWE”, Proc. of Conference on Computer and Communications Security, Vienna, 2006, pp. 1006-1018, doi: https://doi.org/10.1145/2976749.2978425.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Collection "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).
