A Performance Analysis of Root-Converging Methods for Developing Post Quantum Cryptography Algorithms to Mitigate Key-Size-Based Attacks

doi:10.23940/ijpe.23.04.p4.252262

Abstract

Abstract: The upsurge growth of quantum computers poses many threats to existing classical cryptographic algorithms. The polynomials and root-converging methods are found to be suitable for developing a new generation of cryptographic algorithms. Among the many root-convergence methods, the Newton-Raphson is a promising approach according to the literature. It is an approximation method of finding the real root using linear approximation iteratively. Research advancements of the N/R method have improved the performance and space complexities. This research work proposes a new encryption and decryption algorithm for mitigating key size-based attacks using polynomial interpolations and gives a detailed account of various root convergence methods that are being used in the algorithms along with their merits and demerits.

Key words: post quantum cryptography, polynomial-based cryptography, root convergence methods, Newton Raphson method

Taniya Hasija, K. R. Ramkumar, Bhupendra Singh, Amanpreet Kaur, and Sudesh Kumar Mittal. A Performance Analysis of Root-Converging Methods for Developing Post Quantum Cryptography Algorithms to Mitigate Key-Size-Based Attacks [J]. Int J Performability Eng, 2023, 19(4): 252-262.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References

[1] Maqsood F., Ahmed M., Ali M.M., andShah M.A.Cryptography: A Comparative Analysis for Modern Techniques. International Journal of Advanced Computer Science and Applications, vol. 8, no. 6, 2017.
[2] Simmons G.J.Symmetric and Asymmetric Encryption. ACM Computing Surveys (CSUR), vol. 11, no. 4, pp. 305-330, 1979.
[3] Thakur, J. and Kumar, N. DES, AES and Blowfish: Symmetric Key Cryptography Algorithms Simulation Based Performance Analysis. International journal of emerging technology and advanced engineering, vol. 1, no. 2, pp. 6-12, 2011.
[4] Davis R.The Data Encryption Standard in Perspective. IEEE Communications Society Magazine, vol. 16, no. 6, pp. 5-9, 1978.
[5] Biham, E. and Shamir, A.Differential Cryptanalysis of DES-Like Cryptosystems. Journal of CRYPTOLOGY, vol. 4, pp. 3-72, 1991.
[6] Matsui, M. Linear Cryptanalysis Method for DES Cipher. In Advances in Cryptology—EUROCRYPT’93: Workshop on the Theory and Application of Cryptographic Techniques Lofthus, Norway, May 23-27, 1993 Proceedings 12, Springer Berlin Heidelberg, pp. 386-397, 1994.
[7] Lucks, S. Attacking Triple Encryption. In Fast Software Encryption: 5th International Workshop, FSE’98 Paris, France, March 23-25, 1998 Proceedings 5, Springer Berlin Heidelberg, pp. 239-253, 1998.
[8] Lai, X. and Massey, J.L. A Proposal for a New Block Encryption Standard. In Advances in Cryptology—EUROCRYPT’90: Workshop on the Theory and Application of Cryptographic Techniques Aarhus, Denmark, May 21-24, 1990 Proceedings 9, Springer Berlin Heidelberg, pp. 389-404, 1991.
[9] Ranjan, R. and Poonguzhali, I.VLSI Implementation of IDEA Encryption Algorithm.Mobile and Pervasive Computing (CoMPC-2008), 2008.
[10] Sahu H.K., Jadhav V., Sonavane S., andSharma R.K.Cryptanalytic Attacks on International Data Encryption Algorithm Block Cipher. Defence Science Journal, vol. 66, no. 6, 2016.
[11] Hercigonja Z.Comparative Analysis of Cryptographic Algorithms. International Journal of Digital Technology & Economy, vol. 1, no. 2, pp. 127-134, 2016.
[12] Rivest, R.L. The RC5 Encryption Algorithm. In Fast Software Encryption: Second International Workshop Leuven, Belgium, December 14-16, 1994 Proceedings, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 86-96, 2005.
[13] Bhanot, R. and Hans, R.A Review and Comparative Analysis of Various Encryption Algorithms. International Journal of Security and Its Applications, vol. 9, no. 4, pp. 289-306, 2015.
[14] Daemen, J. and Rijmen, V. AES Proposal: Rijndael, 1999.
[15] Kaminsky, A., Kurdziel, M., and Radziszowski, S. An Overview of Cryptanalysis Research for the Advanced Encryption Standard. In 2010-MILCOM 2010 MILITARY COMMUNICATIONS CONFERENCE, IEEE, pp. 1310-1316, 2010.
[16] Deutsch D.Quantum Theory, The Church-Turing Principle and the Universal Quantum Computer. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, vol. 400, no. 1818, pp. 97-117, 1985.
[17] Grover L.K.A Fast Quantum Mechanical Algorithm for Database Search. InProceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212-219, 1996.
[18] Buchmann J.A., Butin D., Göpfert F., andPetzoldt A.Post-Quantum Cryptography: State of the Art.The New Codebreakers: Essays Dedicated to David Kahn on the Occasion of His 85th Birthday, pp. 88-108, 2016.
[19] Chen L., Chen L., Jordan S., Liu Y.K., Moody D., Peralta R., Perlner R.A., andSmith-Tone D., 2016. Report on post-quantum cryptography, Gaithersburg, MD, USA: US Department of Commerce, National Institute of Standards and Technology, vol. 12, 2016.
[20] Alagic G., Apon D., Cooper D., Dang Q., Dang T., Kelsey J., Lichtinger J., Miller C., Moody D., Peralta R., andPerlner R.Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process.US Department of Commerce, NIST, 2022.
[21] Ding, J. and Petzoldt, A.Current State of Multivariate Cryptography. IEEE Security & Privacy, vol. 15, no. 4, pp. 28-36, 2017.
[22] Byröd M., Josephson K., andÅström K.Fast and Stable Polynomial Equation Solving and Its Application to Computer Vision. International Journal of Computer Vision, vol. 84, pp. 237-256, 2009.
[23] Nickalls R.W.D. and Dye, R.H. The Geometry of the Discriminant of a Polynomial. The Mathematical Gazette, vol. 80, no. 488, pp. 279-285, 1996.
[24] Lestari K.E., Pasaribu U.S., Indratno S.W., andGarminia H.Generating Roots of Cubic Polynomials by Cardano'S Approach on Correspondence Analysis. Heliyon, vol.6, no. 6, p. e03998, 2020.
[25] Ehiwario, J.C. and Aghamie, S.O.Comparative Study of Bisection, Newton-Raphson and Secant Methods of Root-Finding Problems. IOSR Journal of Engineering, vol. 4, no. 4, pp. 01-07, 2014.
[26] Kalantari, B. and Park, S.A Computational Comparison of the First Nine Members of a Determinantal Family of Root-Finding Methods. Journal of computational and applied mathematics, vol.130, no. 1-2, pp.197-204, 2001.
[27] Abbasbandy S.Improving Newton-Raphson Method for Nonlinear Equations by Modified Adomian Decomposition Method. Applied mathematics and computation, vol.145, no. 2-3, pp. 887-893, 2003.
[28] Albouy, A. and Fu, Y.Some Remarks About Descartes’ Rule of Signs. Elemente der Mathematik, vol. 69, no. 4, pp. 186-194, 2014.
[29] Grabiner D.J.Descartes' Rule of Signs: Another Construction. The American Mathematical Monthly, vol. 106, no. 9, pp. 854-856, 1999.
[30] Pinkert J.R.An Exact Method for Finding the Roots of a Complex Polynomial. ACM Transactions on Mathematical Software (TOMS), vol. 2, no. 4, pp. 351-363, 1976.
[31] Heindel L.E.Integer Arithmetic Algorithms for Polynomial Real Zero Determination. InProceedings of the second ACM symposium on Symbolic and algebraic manipulation, pp. 415-426, 1971.
[32] Hansen, E. and Patrick, M.A Family of Root Finding Methods. Numerische mathematik, vol. 27, no. 3, pp. 257-269, 1976.
[33] Lang, M. and Frenzel, B.C.Polynomial Root Finding. IEEE Signal Processing Letters, vol. 1, no. 10, pp. 141-143, 1994.
[34] Amat S., Busquier S., andPlaza S.Dynamics of a Family of Third-Order Iterative Methods That Do Not Require using Second Derivatives. Applied mathematics and computation, vol. 154, no. 3, pp. 735-746, 2004.
[35] Chun C.A New Iterative Method for Solving Nonlinear Equations. Applied Mathematics and Computation, vol. 178, no. 2, pp. 415-422, 2006.
[36] Kou J., Li Y., andWang X.Fourth-Order Iterative Methods Free from Second Derivative. Applied mathematics and computation, vol. 184, no. 2, pp. 880-885, 2007.
[37] Sharma, J.R. and Goyal, R.K.Fourth-Order Derivative-Free Methods for Solving Non-Linear Equations. International Journal of Computer Mathematics, vol. 83, no. 1, pp. 101-106, 2006.
[38] Chun C., Lee M.Y., Neta B., andDžunić, J. on Optimal Fourth-Order Iterative Methods Free from Second Derivative and Their Dynamics. Applied mathematics and computation, vol. 218, no. 11, pp. 6427-6438, 2012.
[39] Cordero A.,García-Maimó, J., Torregrosa, J.R., Vassileva, M.P., and Vindel, P. Chaos in King’S Iterative Family. Applied Mathematics Letters, vol. 26, no. 8, pp. 842-848, 2013.
[40] Jarratt P.Some Fourth Order Multipoint Iterative Methods for Solving Equations. Mathematics of computation, vol. 20, no. 95, pp. 434-437, 1996.
[41] Chun, C. and Neta, B.Comparison of Several Families of Optimal Eighth Order Methods. Applied Mathematics and Computation, vol. 274, pp. 762-773, 2016.
[42] Ben-Israel, A. A Newton-Raphson Method for the Solution of Systems of Equations. Journal of Mathematical analysis and applications, vol. 15, no. 2, pp. 243-252, 1966.
[43] King R.F.A Family of Fourth Order Methods for Nonlinear Equations. SIAM journal on numerical analysis, vol. 10, no. 5, pp. 876-879, 1973.
[44] Kung, H.T. and Traub, J.F.Optimal Order of One-Point and Multipoint Iteration. Journal of the ACM (JACM), vol. 21, no. 4, pp. 643-651, 1974.
[45] Maheshwari A.K.A Fourth Order Iterative Method for Solving Nonlinear Equations. Applied mathematics and computation, vol. 211, no. 2, pp. 383-391, 2009.
[46] Neta B.A Sixth-Order Family of Methods for Nonlinear Equations. Int. J. Comput. Math, vol. 7, no. 1997, pp. 157-161, 1979.
[47] Petković M.S., Neta B., Petković L.D., andDžunić J.Multipoint Methods for Solving Nonlinear Equations: A Survey. Applied Mathematics and Computation, vol. 226, pp. 635-660, 2014.
[48] Bi W., Ren H., andWu Q.New Family of Seventh-Order Methods for Nonlinear Equations. Applied Mathematics and Computation, vol. 203, no. 1, pp. 408-412, 2008.
[49] Sharma, J.R. and Arora, H.A New Family of Optimal Eighth Order Methods with Dynamics for Nonlinear Equations. Applied Mathematics and Computation, vol. 273, pp. 924-933, 2016.