.svg){kind=logo}
NONLINEAR DIOPHANTINE EQUATIONS IN CRYPTOGRAPHY ALGEBRAIC APPROACHES TO POST-QUANTUM SECURITY
Keywords:
post-quantum cryptography, nonlinear Diophantine equations, computational hardness (NP-hardness), finite fields, algebraic geometryDOI:
https://doi.org/10.17654/0972555526004Abstract
This paper investigates nonlinear Diophantine equations as a foundation for post-quantum cryptography. Unlike RSA and ECC, which rely on factorization and discrete logarithms vulnerable to Shor’s algorithm, nonlinear systems with mixed degrees (quadratic, cubic, quartic) are NP-hard and lack efficient solutions under classical or quantum computation. We outline a framework where public keys are defined by equation coefficients and private keys exploit trapdoor knowledge of solutions. Encryption embeds plaintext into disguised equations, while decryption applies the trapdoor efficiently. Security analysis shows resistance to Gröbner basis attacks, lattice reductions, and quantum search, positioning these equations as a strong basis for post-quantum cryptographic schemes.
Received: September 10, 2025
Accepted: November 6, 2025
References
[1] P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994.
[2] D. J. Bernstein, J. Buchmann and E. Dahmen, (Eds.), Post-Quantum Cryptography, Springer, 2009.
[3] R. Gupta and V. Sharma, A Diophantine equation based public key cryptosystem, International Journal of Computer Applications 116(9) (2015), 15-18.
[4] J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F4), Journal of Pure and Applied Algebra 139(1-3) (1999), 61-88.
[5] A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen 261(4) (1982), 515-534.
[6] L. Chen et al., Report on post-quantum cryptography, NIST Internal Report 8105, 2016.
[7] S. Kumar and R. Gupta, Complexity of nonlinear Diophantine problems, Mathematics of Computation 93(348) (2024), 765-789.
[8] S. Aggarwal and A. T. Shahida, Solution of exponential Diophantine equation and cryptographic applications, J. Sci. Res. 16(2) (2024), 429-435.
[9] J. H. Silverman, An Introduction to Mathematical Cryptography, Springer, 2020.
[10] B. Buchberger, An algorithm for finding a basis for the residue class ring of a zero-dimensional polynomial ideal, Ph. D. Thesis, 1965.
[11] N. T. Courtois, A. Klimov, J. Patarin and A. Shamir, Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations, EUROCRYPT, 2000.
[12] J. Hoffstein, J. Pipher and J. H. Silverman, An Introduction to Mathematical Cryptography, Springer, 2008.
[13] L. K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 PUSHPA PUBLISHING HOUSE, PRAYAGRAJ, INDIA
This work is licensed under a Creative Commons Attribution 4.0 International License.
_________________________________
Attribution: Credit Pusha Publishing House as the original publisher, including title and author(s) if applicable.
Non-Commercial Use: For non-commercial purposes only. No commercial activities without explicit permission.
No Derivatives: Modifying or creating derivative works not allowed without written permission.
Contact Pusha Publishing House for more info or permissions.
