International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 16, No. 1, 8 Feb. 2024
Cover page and Table of Contents: PDF (size: 1118KB)
Method of Performing Operations on the Elements of GF(2m) Using a Sparse Table
Full Text (PDF, 1118KB), PP.61-72
Views: 0 Downloads: 0
Author(s)
Ivan Dychka
1
Mykola Onai
2,*
Andrii Severin
2
Cennuo Hu
3
Index Terms
Cryptography, Error-correcting Codes, Privacy-preserving, Homomorphic Encryption, Finite Field, Exponentiation, Multiplicative Inverse Element, Galois Field, Sparse Table
Abstract
For the implementation of error-correcting codes, cryptographic algorithms, and the construction of homomorphic methods for privacy-preserving, there is a need for methods of performing operations on elements GF(2m) that have low computational complexity. This paper analyzes the existing methods of performing operations on the elements GF(2m) and proposes a new method based on the use of a sparse table of elements of this field. The object of research is the processes of operations in information security systems. The subject of research is methods and algorithms for performing operations on elements GF(2m). The purpose of this research is to develop and improve methods and algorithms for performing operations on elements GF(2m) to reduce their computational complexity. Empirical methods and methods of mathematical and software modeling are used in the research. Existing and proposed algorithms are implemented using the C# programming language in the Visual Studio 2015 development environment. Experimental research of existing and developed algorithms was carried out according to the proposed method, which allows to level the influence of additional parameters on the results of the research. The conducted research on methods for performing operations on the elements GF(2m) shows the expediency of using a sparse table of field elements. This approach makes it possible to reduce the amount of RAM required for the software and hardware implementation of the developed method compared to the classical tabular method, which requires storage of a full table of correspondence of the polynomial and index representation of the field elements. In addition, the proposed method gives an increase in speed of more than 4 times for the operations of calculating the multiplicative inverse element and exponentiation. As a result, the proposed method allows to reduce the computational complexity of error-correcting codes, cryptographic algorithms, and the homomorphic methods for privacy-preserving.
Cite This Paper
Ivan Dychka, Mykola Onai, Andrii Severin, Cennuo Hu, "Method of Performing Operations on the Elements of GF(2m) Using a Sparse Table", International Journal of Computer Network and Information Security(IJCNIS), Vol.16, No.1, pp.61-72, 2024. DOI:10.5815/ijcnis.2024.01.05
Reference
[1]Darrel Hankerson Guide to Elliptic Curve Cryptography / Hankerson Darrel, Menezes Alfred, Vanstone Scott // Springer-Verlag New York, USA. 2004. 311 p.
[2]Richard Crandall Prime Numbers a Computational Perspective / Crandall Richard, Pomerance Carl// Springer-Verlag New York, USA. 2005. 597 p.
[3]Guerric Meurice de Dormale, Philippe Bulens, Jean-Jacques Quisquater Efficient Modular Division Implementation ECC over GF(p) Affine Coordinates Application / Meurice de Dormale Guerric, Bulens Philippe, Quisquater Jean-Jacques // The 14th International Conference on Field Programmable Logic and Applications, FPL 2004, Volume 3203 of Lecture Notes in Computer Science. 2004. Pp. 231-240.
[4]Hazzazi, M.M.; Attuluri, S.; Bassfar, Z.; Joshi, K. A Novel Cipher-Based Data Encryption with Galois Field Theory. Sensors 2023, 23, 3287. https://doi.org/10.3390/s23063287
[5]Akira Ito, Rei Ueno, and Naofumi Homma Efficient Formal Verification of Galois-Field Arithmetic Circuits Using ZDD Representation of Boolean Polynomials / IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 41, No. 3, March 2022.
[6]Donald E. Knuth Art of Computer Programming, Volume 2: Seminumerical Algorithms / Knuth Donald // 3rd Edition by Addison-Wesley Professional, Canada. 1997. 784 p.
[7]Richard E. Blahut Theory and Practice of Error Control Codes / Blahut Richard E. // Addison-Wesley. 1983. 500 p.
[8]Henri Cohen A Course in Computational Algebraic Number Theory / Cohen Henri // Springer Science & Business Media. 1993. 534 p.
[9]S. Parthasarathy Multiplicative inverse in mod(m) / Parthasarathy S. // Algologic Technical Report #1/2012. 2012. P. 1-3.
[10]Robert Lorencz New Algorithm for Classical Modular Inverse/ Lorencz Robert // Cryptographic Hardware and Embedded Systems. International Workshop. 2002. P. 57-70.
[11]Wolfram Math World: http://mathworld.wolfram.com/CarmichaelFunction.html
[12]W. Fischer Note on fast computation of secret RSA exponents / Fischer W., Seifert J.-P. // Information Security and Privacy (ACISP 2002), vol. 2384 of Lecture Notes in Computer Science, Springer-Verlag. 2002. Pp. 136–143.
[13]Akram A. Moustafa Fast Exponentiation in Galois Fields GF(2m) Using Precomputations / Contemporary Engineering Sciences, Vol. 7, 2014, no. 4, 193 – 206
[14]Suleimenov IE, Vitulyova YS, Matrassulova DK (2023) Features of digital signal processing algorithms using Galois fields GF(2n+1). PLoS ONE 18(10): e0293294. https://doi.org/10.1371/journal.pone.0293294
[15]I. Suleimenov, Y. Vitulyova and A. Bakirov, "Hybrid Number Systems: Application for Calculations in Galois Fields," 2022 3rd Asia Conference on Computers and Communications (ACCC), Shanghai, China, 2022, pp. 126-130, doi: 10.1109/ACCC58361.2022.00028.