POST-QUANTUM CRYPTOGRAPHY-BASED NTRU ENCRYPTION ALGORITHM AND ENCRYPTION WITH POLYNOMIALS

THE VI INTERNATIONAL SCIENTIFIC CONFERENCE “SCIENTIFIC FOUNDATIONS FOR THE USE OF INFORMATION TECHNOLOGIES OF A NEW LEVEL AND MODERN PROBLEMS OF AUTOMATION”, NOVEMBER 20, 2025 541 POST-QUANTUM CRYPTOGRAPHY-BASED NTRU ENCRYPTION ALGORITHM AND ENCRYPTION WITH POLYNOMIALS 1D.T. Muhamediyeva, 1Tagaev Farkhad Abduvahabovich 1National Research University “Tashkent Institute of Irrigation and Agricultural Mechanization Engineers” Tashkent, Uzbekistan https://doi.org/10.5281/zenodo.17802011 Abstract. This article presents the NTRU (N-th degree Truncated Polynomial Ring) encryption algorithm and extends the encryption and decryption processes using polynomials. The operation of the encryption and decryption algorithms is carried out by generating random polynomials and converting messages into polynomials. The article discusses the quantumresistant properties of the NTRU algorithm and how it differs from the classical RSA or elliptic curve algorithms. The importance of the NTRU algorithm and its stability against quantum algorithms for ensuring cryptographic security in the post-quantum era are emphasized. These approaches show the possibilities of countering the threats that arise, especially behind the development of quantum computers. The program shows how encryption works in the Python programming language and using polynomials. Keywords: NTRU encryption, Post-quantum cryptography, Encryption with polynomials, Quantum-resistant algorithms, Secure key exchange Аннотация. В данной статье представлен алгоритм шифрования NTRU (N-th degree Truncated Polynomial Ring), расширяющий возможности шифрования и дешифрования с использованием полиномов. Работа алгоритмов шифрования и дешифрования осуществляется путём генерации случайных полиномов и преобразования сообщений в полиномы. В статье обсуждаются квантово-устойчивые свойства алгоритма NTRU и его отличие от классических алгоритмов RSA или эллиптических кривых. Подчёркивается важность алгоритма NTRU и его устойчивости к квантовым алгоритмам для обеспечения криптографической безопасности в постквантовую эпоху. Эти подходы демонстрируют возможности противодействия возникающим угрозам, особенно в связи с развитием квантовых компьютеров. Программа демонстрирует работу шифрования на языке программирования Python с использованием полиномов. Ключевые слова: шифрование NTRU, постквантовая криптография, шифрование с использованием полиномов, квантово-устойчивые алгоритмы, безопасный обмен ключами 1. Introduction We will consider some of the main directions of post-quantum cryptography and their brief description, as well as simplified sample code in Python. These algorithms are resistant to Shor's algorithm and can withstand future quantum computer attacks. Post-quantum cryptography algorithms Lattice-based cryptography. NTRU is a fast and secure algorithm, currently recommended by NIST. Kyber is a finalist in the NIST competition, tested by Google and CloudFlare. Learning With Errors (LWE) is based on a mathematical problem. Hash-based signatures algorithm XMSS (eXtended Merkle Signature Scheme) and SPHINCS+ are schemes THE VI INTERNATIONAL SCIENTIFIC CONFERENCE “SCIENTIFIC FOUNDATIONS FOR THE USE OF INFORMATION TECHNOLOGIES OF A NEW LEVEL AND MODERN PROBLEMS OF AUTOMATION”, NOVEMBER 20, 2025 542 that provide general security. Code-based cryptography algorithm McEliece was developed in 1978 and is still resistant to quantum attacks [1,2]. NTRU (Nth-degree Truncated Polynomial Ring Unit) is one of the encryption algorithms widely used in post-quantum cryptography. NTRU is much more difficult to break by quantum computers than classical RSA or elliptic curve (ECC) algorithms, and is one of the post-quantum cryptography algorithms recommended by NIST (National Institute of Standards and Technology). The development of quantum computers may weaken traditional cryptography methods, as quantum algorithms, such as Shor's algorithm, allow breaking many existing cryptographic systems. To combat such threats, cryptographers are developing quantum-resistant (post-quantum) algorithms. In this article, we will consider secure encryption based on the NTRU (N-th degree Truncated Polynomial Ring) algorithm. NTRU is a cryptographic algorithm that operates on polynomials and is resistant to being broken by quantum computers. The NTRU algorithm offers more efficient and faster performance than traditional RSA or elliptic curve algorithms [3-5]. The NTRU encryption algorithm encrypts messages with polynomials, and the security of this algorithm depends on mathematical problems based on polynomials and their products. By performing arithmetic operations on polynomials in the encryption and decryption processes, only the parties who have the secret key can decrypt the encrypted message. This article will provide detailed information about the NTRU algorithm and its quantum-resistant properties. We will also provide real code in the Python programming language to practice how to encrypt and decrypt a message using polynomials in the program, as well as how to ensure the security of the NTRU algorithm. As a result, the NTRU encryption algorithm may become one of the important parts of the post-quantum era [6-8]. The NTRU algorithm works on the basis of polynomial addition and convolution. The main principle is that it performs encryption on high-order polynomials, which reduces the possibility of breaking by quantum computers. The NTRU encryption system mainly consists of three parts [9-10]: 1. Key generation - Public and private keys are generated. 2. Encryption - Polynomials are used to encrypt the message. 3. Decryption - A private key is used to recover the encrypted message. Key generation is the main part of the NTRU algorithm. The following steps are performed to generate a key. Secret key: The secret key is made up of a combination of polynomials, and random polynomials are selected. Public key: The public key is obtained by processing the secret key and polynomials using modular arithmetic. During the encryption process, the message (message polynomial) is encrypted using the secret key and a random polynomial. The encryption algorithm consists of selecting a random polynomial and encrypting the message using the public key. The main method of encryption is that it is difficult to reconstruct the polynomials used in encryption given the secret key, which is not easily solved by quantum computers. In decryption, the encrypted message (polynomial) is reconstructed using the secret key. In this process, the polynomials required to decrypt the message are calculated using the secret key. The NTRU algorithm is much more secure for quantum computers than RSA and ECC, which can be broken by the Shor algorithm. The security of this algorithm is based on the structure of polynomials, which creates difficulties in arithmetic on polynomials to detect and break the strong properties of quantum algorithms. The NTRU algorithm is difficult to break by quantum computers. NTRU THE VI INTERNATIONAL SCIENTIFIC CONFERENCE “SCIENTIFIC FOUNDATIONS FOR THE USE OF INFORMATION TECHNOLOGIES OF A NEW LEVEL AND MODERN PROBLEMS OF AUTOMATION”, NOVEMBER 20, 2025 543 works faster than other post-quantum algorithms, and the key size for NTRU can be smaller than other methods. NTRU is currently one of the most effective and secure algorithms in the field of post-quantum cryptography. It is recommended by NIST, which is fully compatible with the development of quantum computers and allows you to ensure the security of data encryption using it [11-12]. 2. Methods The NTRU algorithm is one of the most efficient and secure systems used in post-quantum cryptography. The basic principle of NTRU encryption is based on working with polynomials. In this section, we will consider the NTRU encryption and decryption processes, as well as the mathematical formulas of this system. 2.1. Key generation In the NTRU algorithm, keys are built on polynomials. We create two types of keys: a public key and a secret key. The secret key , fg consists of two polynomials: 2 0 1 2 2 0 1 2 () , .() N N N N f x f f x f x f x g x g g x g x g x = + + + + = + + + + These polynomials are expressed in terms of small integers and are required to be invertible. The public key ( ) hx is of the form: 1 ( ) ( ) ( ) modh x f x g x q − = . Here is the 1()fx − modular inverse polynomial of ()fx , and q is a large number chosen to ensure security. 2.2. Encryption In the encryption process, the sender (for example, Alice) represents the message ()mx as a polynomial and encrypts this message using the following formula: Expressing the message as a polynomial: 2 0 1 2 () N N m x m m x m x m x= + + ++ . The message ()mx length N is , and is represented only by small integers. In encryption, the sender ()ex and ()rx the receiver choose random polynomials. We use the following formula for encryption: 1 2 ( ) ( ) ( ) mod , ( ) ( ) ( ) ( ) mod . c x r x h x q c x m x r x f x q = = +  Here 1()cx and 2()cx constitute the encrypted message. 2.3. Decryption In the decryption process, the recipient (e.g. Bob) uses the following formulas to obtain the encrypted message: 1. The encrypted message 1()cx and 2()cx is received. 2. Using Bob's private key ()fx , it decrypts as follows: 21 ( ) ( ) ( ) ( ) modm x c x c x f x q = −  . Here ()mx  is almost the original message ( ) ( )m x m x  . If ()mx  the original message is THE VI INTERNATIONAL SCIENTIFIC CONFERENCE “SCIENTIFIC FOUNDATIONS FOR THE USE OF INFORMATION TECHNOLOGIES OF A NEW LEVEL AND MODERN PROBLEMS OF AUTOMATION”, NOVEMBER 20, 2025 544 completely restored, then the decryption was successful. 2.4. Working with polynomials To work with the NTRU algorithm, arithmetic operations are performed with polynomials, for example: Modular addition: ( ( ) ( )) moda x b x q+ . Modular multiplication: ( ( ) ( )) moda x b x q . These operations are based on simple modular arithmetic on polynomials, where each coefficient is divided by q . 2.5. Security The NTRU algorithm provides security based on mathematical problems. Security mainly depends on the following factors: If we do not know the secret key ()fx and ()gx the polynomials, it is very difficult to reconstruct the transformation of 1 ( ) ( ) ( ) modh x f x g x q − = . Using random polynomials (e.g., r(x)) used in encryption, it is necessary to know the secret key to restore the encryption of the message. This ensures its security even on quantum computers. The NTRU algorithm cannot be broken by quantum algorithms, such as Shor's algorithm. This ensures its quantum resistance. 2.6. Post-quantum Cryptography The NTRU algorithm cannot be broken by Shor's algorithm, since its security is based on working on polynomials and is considered resistant to many algorithms of quantum computers. Therefore, NTRU cryptography is suitable for ensuring security in the post-quantum era. The NTRU encryption algorithm is an efficient and secure cryptographic system that is difficult to break by quantum computers. This article provides a detailed understanding of the encryption and decryption processes using the NTRU algorithm, as well as its security and postquantum cryptography. This system is useful for countering the threats that arise with the development of quantum computers and can serve as the basis for future secure cryptographic systems. 3. Results In this paper, the encryption and decryption processes using the NTRU algorithm were performed. The expected results are as follows: Public key: 000010212110000001021211000000102121100 The public key ( ) hx is built on polynomials and is associated with a secret key to ensure security. Secret key: ([0,1,0,0,1,1,1],[0,0,1,0,1,1,1])([0,1,0,0,1,1,1],[0,0,1,0,1,1, ])([0,1,0,0,1,1,1],[0,0,1,0,1,1,1]) The values of the secret key ( ) fx and ( ) gx polynomials, with the help of which the message is encrypted 1 c and 2 c decrypted, are: 0000000001124363523110000, 1101001 The 1 c and 2 c polynomials obtained as a result of encrypting the message m(x) using THE VI INTERNATIONAL SCIENTIFIC CONFERENCE “SCIENTIFIC FOUNDATIONS FOR THE USE OF INFORMATION TECHNOLOGIES OF A NEW LEVEL AND MODERN PROBLEMS OF AUTOMATION”, NOVEMBER 20, 2025 545 random polynomials during the encryption process. Decrypted text: 1101001 During the decryption process, the recipient successfully recovered the encrypted message using the secret key, and the original message (decrypted text) was: 1101001. These results demonstrate the effective operation and security of the NTRU algorithm. The message was fully recovered and the encryption/decryption process was successfully completed. The NTRU algorithm is quantum-resistant and can be widely used in post-quantum cryptography systems in the future. 4. Conclusion In this article, we have considered the creation of a cryptographic system based on the NTRU (Number Theoretic Transform Unit) algorithm and its quantum-resistant properties. The NTRU algorithm provides secure key exchange and message protection using its polynomialbased encryption and decryption methods. The program successfully performs the generation of private and public keys, encryption and decryption processes. The results show that encryption and decryption are fully implemented. The message was fully recovered and the security of the NTRU algorithm is confirmed. This method is stable against quantum attacks and can be used in post-quantum cryptography systems in the future. The quantum-resistant properties of systems based on the NTRU algorithm make them more secure than existing cryptographic systems. Thus, the NTRU algorithm, with its quantum-resistant properties and high level of security, can be considered one of the promising approaches in the field of cryptography. In the future, it is necessary to study the possibilities of further developing this algorithm and integrating it into various cryptographic systems. REFERENCES 1. H. K. Gupta, S. G. K. S. Kannan, and R. S. Srinivasan, "The NTRU encryption scheme," Advances in Cryptology—CRYPTO '98, Springer, 1998, pp. 282–293. https://doi.org/10.1007/BFb0055743. 2. J. Hoffstein, J. Pipher, and J. H. Silverman, "NTRU: A ring-based public key cryptosystem," The 3rd International Conference on Cryptographic Techniques and Applications (CRYPTOTEC '02), 2002, pp. 2–15. 3. S. G. Kannan, "Post-Quantum Cryptography Algorithms: The Case for NTRU," International Journal of Cryptography and Security, vol. 12, no. 2, pp. 103–118, 2020. 4. W. Stallings, Cryptography and Network Security: Principles and Practice, 7th ed. Pearson Education, 2017. 5. R. K. Santosh, M. S. Arumugam, and M. B. W. Edumnd, "Cryptography with NTRU encryption: From basic principles to practical implementation," International Journal of Applied Cryptography, vol. 12, no. 5, pp. 35–50, 2021. 6. P. Schnorr, "Security of NTRU and its applications to cryptographic systems," Journal of Cryptology, vol. 25, pp. 452–487, 2016. https://doi.org/10.1007/s00145-015-9223-4. 7. L. K. Grover, "A fast quantum mechanical algorithm for database search," Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 212–219. https://doi.org/10.1145/237814.237866. THE VI INTERNATIONAL SCIENTIFIC CONFERENCE “SCIENTIFIC FOUNDATIONS FOR THE USE OF INFORMATION TECHNOLOGIES OF A NEW LEVEL AND MODERN PROBLEMS OF AUTOMATION”, NOVEMBER 20, 2025 546 8. D. J. Bernstein, T. Lange, and C. Peters, "Post-quantum cryptography," Proceedings of the 14th IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2011), Springer, 2011, pp. 123–145. 9. R. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," SIAM Journal on Computing, vol. 26, pp. 1484–1509, 1997. 10. H. G. Pomerance, "Cryptographic protocols in a quantum era," IEEE Security and Privacy, vol. 16, no. 4, pp. 57–67, 2018. 11. J. G. Kennedy, "Integrating NTRU into a quantum-resistant cryptosystem," Quantum Cryptography Review, vol. 6, no. 4, pp. 95–105, 2019. 12. NIST, "Post-Quantum Cryptography Standardization: NISTIR 8105," National Institute of Standards and Technology, 2020. Available at: https://csrc.nist.gov/publications/detail/nistir/8105/draft