Families of Square Commutative 2х2 Matrices

Abstract

The objective of this study is to define and investigate the families of square matrices of order 2 with a commutative multiplication operation to be used in cryptographic information transformation. The general linear group of order n over the prime field of integers modulo p has been investigated. Six families of matrices from the general linear group of order 2 for which the multiplication operation is commutative have been defined. The current study has found the cardinalities of these families. The study has also regarded the family of matrices from the general linear group of order 2 with a commutative multiplication operation, extended by an identity matrix. The research has revealed that this matrix family is a multiplicative abelian group. For this purpose, the authors have proved that the axioms of the group are fulfilled, confirmed that the multiplication is commutative, and demonstrated the order of the group. The results of this study create prerequisites for using the obtained multiplicative abelian groups of square matrices of order 2 while solving the tasks of constructing cryptographic key agreement protocols, asymmetric encryption algorithms, and three-pass cryptographic protocols.

Keywords

• 1 Matrix family
• commutative transformation
• commutative encryption
• multiplicative abelian group
• key agreement
• cryptography

1. Introduction

Commutative operations play an essential role in cryptographic information transformation algorithms widely used in modern information and communication systems, smart technologies, and the Internet of Things. In particular, key agreement procedures, asymmetric encryption, and three-pass cryptographic protocols apply commutative cryptographic transformations [ 1–5 ]. Some of the classic cryptographic schemes that deploy commutative exponentiation in modular arithmetic (modular exponentiation) are the

Diffie-Hellman key agreement protocol [6], RSA

[ 7 ], SRA [ 8 ], Massey-Omura cryptosystem [ 9 ].

The scientific search for commutative cryptographic transformations is still relevant today. Algorithms whose strength relies on the computational complexity of factorization and discrete logarithm procedures are not protected against attacks with quantum computers and can be broken over polynomial time [ 10 ].

Moldovyan et al. [ 11 ] refer to the literature [12] as one of the first attempts to solve the problem of building a post-quantum commutative cipher. The proposed approach is based on the hidden discrete logarithm problem, however, this approach does not achieve an increase in cryptographic strength [13]. Methods for applying forms of the hidden discrete logarithm problem have been developed in studies [14–16] and are based on operations in a multidimensional vector space.

In the study [14], the authors propose a secure encryption method based on commutative transformations. The three basic components

of this method are the following cryptographic protocols: Diffie-Hellman key agreement protocol [ 6 ], Pohlig-Hellman commutative encryption algorithm [17], and Shamir threepass protocol [ 8 ]. An exponentiation cipher is used to perform commutative encryption.

Kryvyi [18] has demonstrated a method for

constructing a symmetric cryptosystem based on the properties of finite associativecommutative rings with unity and discusses conditions for using discrete logarithm functions in the rings.

The study [19] develops encryption using

cryptography methods such as Diffie-Hellman, commutative supersingular isogeny, and group action inverse problems.

Examples of using commutative encryption

to protect secret key exchange are offered in the studies [20–21]. Research undertaken by

Sihare [22] further develops the schemes and offers a dynamic multi-party quantum key agreement protocol.

Studies [23–26] use permutations to

represent data, and operations on permutations to construct key agreement protocol [27] and to improve three-pass cryptographic protocol, including for use in noisy channels [28–30].

A previous study [31] suggests using publickey cryptography based on commutative semirings of tropical circular matrices, where multiplication is the ordinary addition of numbers and there is no ordinary multiplication of numbers in the tropical semiring.

Shamir’s three-pass random matrix

ciphering mechanism [32] uses a three-pass protocol with encryption operators that are random commutative matrices.

The current study focuses on identifying and researching families of square matrices with commutative multiplication. The matrices will be limited by 2×2 dimension, and their elements will belong to the prime field of integers modulo p. 2. Families of Commutative 2×2

Matrices

We first introduce a definition.

Definition 1 [ 33–34 ]. A general linear group of order n over any field F or ring R is a group of invertible matrices n  n containing elements from F (or R ) with ordinary matrix fixed, fixed,    1 3 = t     0 ak +1 a  t, a, k  Z p ,t  0, ,  , k is ak +1  0  multiplication as the group multiplication operation.

GL (n, F ) will denote the general linear group of order n over the field F .

Note that the square matrix A is invertible if

and only if its determinant A  0 [ 35 ].

Here, we consider the group   a b    =  A =  , a,b,c, d  Z p , A  0 , where   c d  

Z p is the prime field of integers modulo p .

Then,  = GL (2, Z p ) .

Theorem 1. Multiplication is commutative for the following families of matrices  :   1 0   1 = t   0 a ,t, a  Z p ,t  0, a  0 ,    1 2 = t     a ak + 1 0  t, a, k  Z p ,t  0, ,  , k is

ak + 1  0     a 1  t, a,b  Z p , 4 = t   ,  , a , b are fixed,   b 0  t  0,b  0     0 1  t, a,b  Z p , 5 = t   ,  , a , b are fixed,   b a  t  0,b  0    a 1  t, a,b, k  Z p ,t  0,b  0, 6 = t   b a + k , a (a + k ) − b  0  , b , k are fixed.

Proof.

Note that in the general case,  is non

abelian.

Consider the following cases:

b = c = 0 , ad  0 b = 0 or c = 0 , ad  0 bc  0 , ad = 0 ad  0 , bc  0 .

Case 1: b = c = 0 , ad  0 .

In this case,

 a b   a 0   1 0  A =   =   = a   . The set of  c d   0 d   0 d a  such diagonal non-degenerate matrices is equivalent to the set   1 0   1 = t   0 a ,t, a  Z p ,t  0, a  0 , which forms an abelian group [ 36 ]: for A, B  1 , AB = BA is true.

Case 2: b = 0 or c = 0 , ad  0 .

Let b = 0 and ad  0 . Then, matrix  a b   a 0   1 0  A =   =   = a   . The set of  c d   c d   c a d a  such matrices is a family of nondegenerate lower triangular matrices   1 0 t, a,b  Z p ,  = t   , . According to [ 36 ],   a b  t  0,b  0   forms a group by multiplication.

 1 0  1 0  Let A, B and A =   , B =   .

 a b   x y   1 0  The product A  B =  a + bx by . The product  1 0  B  A =  x + ay by  .

Value

A B = B  A , if a + bx = x + ay or x (b −1) = a ( y −1) . If a = x = 0 ,  degenerates into 1 , which is abelian. If a, x  0 , we assume that b −1 y −1

= a x b = ak +1, = k , k  Z p . Then 

 y = xk +1;  1 0   1 0  and matrices A =   a ak +1 , B =   x xk +1 , where a  0 , x  0 , ak +1  0 , xk +1  0 , k  Z p .

  1 0  t, a, k  Z p ,t  0,

Then 2 = t   a ak +1, ak +1  0  is an abelian group, where a and t values may be arbitrary, while k value is a fixed parameter of group 2 .

Adopting that c = 0 , ad  0 , and reasoning by analogy, we can prove that a group of nondegenerate upper triangular matrices of  a b  A =   type is abelian if it forms the group  0 d    1  3 = t  

  0 ak +1 Case 3: bc  0 , ad = 0 .

Let bc  0 and d = 0 .

 a b   a b   a b 1 A =   =   = a   .

 c d   c 0  c b 0 a  t, a, k  Z p ,t  0, ,  .

ak +1  0 

Then

Such

 a 1  A = 

 b a + k  , matrices define    a 1  t, a,b  Z p ,  = t   ,  .

  b 0 t  0,b  0     a 6 = t     b a + k  1  t, a,b, k  Z p ,t  0,b  0, ,  is a (a + k ) − b  0 

 a 1   x 1  Let A, B and A = t   , B = s    b 0  y 0 . An equality A B = B  A means  ax + y a   ax + b x  x = a,  bx b  =  ay y  or  y = b. Therefore, if bc  0 and d = 0 the commutative    a 1 t, a,b  Z p , family is the set 4 = t   ,  ,   b 0 t  0,b  0  where a and b are fixed.

Taking bc  0 , a = 0 , it can be shown by analogy that the commutative family is the set    0 1  t, a,b  Z p , 5 = t   ,  , where a and b   b a  t  0,b  0  are fixed.

Note that the families 4 , 5 are not closed

under multiplication, so they do not form a group.

Case 4: ad  0 , bc  0 .

 a b   a b 1  Since b  0 , A =   = b  .

 c d   a c a d  The set of such matrices forms the set of nondegenerate matrices    a 1 t, a,b,c  Z p ,t  0,  = t   ,   b c  b  0, ac − b  0  .

 a 1  x 1  Let A, B and A =   , B =   .

 b c   y z   ax + y a + z  The product A  B =  bx + cy b + cz  . The  ax + b x + c  product B  A =  ay + bz y + cz  . is achieved if

Equality A B = B  A ax + y = ax + b; a + z = x + c;  bx + cy = ay + bz; b + cz = y + cz.

Let c − a = z − x = k ,  y = b;

It follows that 

c − a = z − x. k  Z p .

 x 1  B =   b x + k  ,

Then

and a commutative family, wherein a and t values may be arbitrary, while b and k values are 6 fixed parameters.

Now, we have got all 1 − 6 families of

matrices from  = GL (2, Z p ) , which multiplication is commutative.

The theorem is proved.

The cardinality of each 1 − 3 family is equal to ( p −1)2 , and the cardinality of each 4 − 5 family is equal to p −1, while the cardinality of 6 family is ( p −1)( p − l ) , where l = 0;1;2 is the number of integer roots of the equation a2 + ka − b = 0(mod p) concerning the variable a . The l value is defined by b and k parameters. 3. Commutative Family of 2×2

Matrices with Identity Matrix Consider the matrix family 6 supplemented by an identity matrix, as well as the case when b = 0 , since it does not affect the commutativity of the matrices from 6 . We will denote this family by   a 1   1 0  t   b a + k , s   ,  0 1   CGLb,k (2, p ) =  t, s, a,b, k  Z p ,t, s  0, .

 a (a + k ) − b  0 

Theorem 2. The matrix family

CGLb,k (2, Z p ) is a commutative (abelian) group under multiplication.

Proof.

We will prove that the group axioms are

fulfilled for CGLb,k (2, Z p ) and demonstrate that the multiplication CGLb,k (2, Z p ) is commutative. operation in  1 0 element: E =   .

 0 1 

2. The operation of multiplying elements in

CGLb,k (2, Z p ) is associative since this is a general property for matrices.

3. For each matrix ACGLb,k (2, Z p ) , there is an inverse matrix A A−1 = A−1  A = E .

Thus, if

A−1 CGLb,k (2, Z p ) :

 1 0 A = s    ,  0 1  then A−1 = s   1 0−1   . In Z p , for  = s−1   1 0   0 1  0 1 each s  Z p , there is an inverse element s−1 : s  s−1 = s−1  s = e =1, that is unique. Further, while proving this theorem, we will neglect multipliers s and t without limiting the generality of the foregoing.

 a 1  Let A = 

 b a + k  .

Then

A−1 =  ba a +1 k −1 = a (a +1k ) − b  a−+bk −a1 .

Let us assume that t ' = −1 a (a + k ) − b  0 , a' = −a − k . Then, A−1 = t '  ab' a '1+ k  CGLb,k (2, Z p ) .

Moreover, it follows therefrom that  a 1  c 1 −1  b a + k  b c + k  = E if and only if a = c .  is closed under 4.

CGLb,k (2, Z p ) multiplication. this property is obvious.

Let A, B CGLb,k (2, Z p ) . If A = E or B = E , Consider the situation when A =  a 1   b a + k   x 1   b x + k  for arbitrary a, x  Z p . and B =   a 1  x 1  A  B = 

 b a + k  b x + k  =  ax + b a + x + k  =  b(a + x + k ) b + (a + k )( x + k ) .

If

 ax + b A  B = 

 0

Since

A  0 a + x + k = 0 , 0   1 0 ax + b  = (ax + b)    .

 0 1  and B  0 , then then 1. CGLb,k (2, Z p ) has a single identity

Product

A  B = A  B  0 and ax + b  0 correspondingly. From whence it follows that A  B CGLb,k (2, Z p ) .

If a + x + k  0 , then A  B = 1  aa+xx++bk 1  . Let a + x + k  b k + aa+xx++bk  t = 1  0 and a + x + k  y 1   b y + k  CGLb,k (2, Z p ) .

A  B = t  y = ax + b . Then a + x + k 5. CGLb,k (2, Z p ) is an abelian group.

If A = E , then A B = E  B = B = B  E = B  A

Let A =  a 1   x 1   b a + k  and B = 

 b x + k  .

 ax + b a + x + k  Then A  B =  b(a + x + k ) b + (a + k )( x + k ) and B  A =  b(aa+x +x b+ k ) b + (ax ++ kx)+(ak + k ) , from where it follows that A B = B  A .

The theorem is proved.

To exponentiate the square matrix

 a b  A =   , we will use the following  c d  expression from [ 37 ]:

An =  un+1 − dun  cun

bun  un+1 − aun  , (1) where un+1 = (a + d )un − A un−1 = tr ( A)un − A un−1 , tr ( A) is a trace of the matrix A [ 38 ]; u0 = 0 , u1 = 1 .

For a matrix

 a 1   b a + k  CGLb,k (2, Z p ) , A =  group

element we obtain tr ( A) = 2a + k ,

A = a (a + k ) − b  0 . Then un+1 = (2a + k )un − (a (a + k ) − b)un−1 and An =  un+1 − (a + k )un

 bun Note that An = A n  0 .

un  . un+1 − aun 

Since CGLb,k (2, Z p ) is a commutative group under multiplication,

According to (1): If

An =  un0+1

If un = 0 , then 0   1 0 un+1  = un+1  0 1  CGLb,k (2, Z p ) . un  0 , then An CGLb,k (2, Z p ) .

An = un  uunn+1 − a − k 1   CGLb,k (2, Z p ) .   b uunn+1 − a 

Theorem 3. The order of the matrix group

CGLb,k (2, Z p ) for D = k 2 + 4b  u2  Z p is p2 −1.

Proof.

It is appropriate at this point to recall that

  a 1   1 0  CGLb,k (2, p ) =  t,sb, a,ba,+k kZ, sp ,t, s  0, . t   ,

 0 1    a (a + k ) − b  0 

Values b and k are fixed for the group, then t, a, s  Z p , t, s  0 are variable. Then, the number of different values that matrices  a 1  t  

 b a + k  may take on is equal to the number of different possible pairs t, a with the given restraints. The value t may take on p −1 different values from p (t  0) . Value a is restricted by the condition a (a + k ) − b  0 . For D = k 2 + 4b  u2  Z p , this equation does not have integer roots concerning the variable a , therefore, it can take on p different values with Z p .

The number of different values that matrices

 1 0 s    may take on is equal to the number  0 1  p −1 of different possible values s  Z p , s  0 .

Therefore, the order of the matrix group

CGLb,k (2, Z p ) is ( p −1) p + p −1 = p2 −1.

The theorem is proved. 293

Thus, for

D = k 2 + 4b  u2  Z p .

CGLb,k (2, Z p ) is a multiplicative abelian group of order p2 −1.

Remark 1 [ 39 ]. For prime p  3 , the number of nonzero values D  Z p : D = u2  Z p and the number of D  Z p : D  u2  Z p values coincide and are equal to

4. Conclusion

p −1 2

The paper defines six families of matrices from

the general linear group GL (2, Z p ) with order

2 over the prime field of integers modulo p

with commutative multiplication operation.

The set cardinality for the defined families has

been determined.

The research results indicate that the matrix   a 1    t   ,  set   b a + k   supplemented by the t, a,b, k  Z p ,t  0, a (a + k ) − b  0  matrix set s   1 0 

, s  Z p , s  0 forms an   0 1   abelian group under multiplication. The order of this group is p2 −1.

Further studies of square matrix groups

commutative under multiplication, may involve the selection of matrix parameters, as well as their application in cryptographic transformation operations.

5. Acknowledgments

This research was funded by the Ministry of

Education and Science of Ukraine under grant 0123U100270.

[12] D. Moldovyan, Non-Commutative Finite Systems, Sensors 22(14) (2022). doi: Groups as Primitive of Public-Key 10.3390/s22145391.

Cryptoschemes, Quasigroups Relat. Syst. [24] J. Al-Azzeh, et al. Permutation-Based 18(2) (2010) 165–176. Frame Synchronization Method for Data [13] A. Kuzmin, et al., Cryptographic Transmission Systems with Short Algorithms on Groups and Algebras, J. Packets, Egyptian Inform. J. 23(3) (2022) Math. Sci. 223(5) (2017) 629–641. doi: 529–545. doi: 10.1016/j.eij.2022.05.005. 10.1007/s10958-017-3371-y. [25] E. Faure, A. Shcherba, B. Stupka, [14] N. Nguyen, et al., No-Key Protocol for Permutation-Based Frame Deniable Encryption, Inf. Syst. Des. Intel. Synchronisation Method for Short Appl. 672 (2018) 96–104. doi: Packet Communication Systems, 11th 10.1007/978-981-10-7512-4_10. IEEE Int. Conf. Intell. Data Acquisition [15] D. Moldovyan, et al., Post-quantum Adv. Comput. Syst. Technol. Appl. (2021) Commutative Encryption Algorithm, 1073–1077. doi: 10.1109/IDAACS53288. Context-Aware Systems and 2021.9660996.

Applications, and Nature of Computation [26] J. Al-Aazzeh, et al., Telecommunication and Communication (2019) 205–214. Systems with Multiple Access Based on doi: 10.1007/978-3-030-34365-1_16. Data Factorial Coding, Int. J. Commun. [16] N. Moldovyan, A. Moldovyan, Antenna Propagation 10(2) (2020) 102– V. Shcherbacov, Post-Quantum No-Key 113. doi: 10.15866/irecap.v10i2.17216. Protocol, Buletinul Academiei de Stiinte [27] E. Faure, et al., Cryptographic Key a Republicii Moldova, Matematica 85(3) Exchange Method for Data Factorial (2017) 115–119. Coding, in: International Workshop on [17] M. Hellman, S. Pohlig, Exponentiation Cyber Hygiene vol. 2654 (2020) 643–

Cryptographic Apparatus and Method, 664.

(1984). [28] E. Faure, et al., Concept for Using [18] S. Kryvyi, Application of Commutative Permutation-Based Three-Pass Rings with Unity for Construction of Cryptographic Protocol in Noisy Symmetric Encryption System, Cybern Channels, Systems, Decision and Control Syst. Anal. 58(3) (2022) 319–330. doi: in Energy V (2023) 99–113. doi: 10.1007/s10559-022-00464-z. 10.1007/978-3-031-35088-7_7. [19] K. Dey, et al., A Post-Quantum [29] E. Faure, et al., A Method for Reliable Signcryption Scheme Using Isogeny Permutation Transmission in ShortBased Cryptography, J. Inf. Secur. Appl. Packet Communication Systems, 69 (2022). doi: 10.1016/j.jisa.2022.1032 Information Technology for Education, 80. Science, and Technics (2023) 177–195. [20] Z. Sun, J. Huang, P. Wang, Efficient doi: 10.1007/978-3-031-35467-0_12.

Multiparty Quantum Key Agreement [30] A. Shcherba, E. Faure, O. Lavdanska, Protocol Based on Commutative Three-Pass Cryptographic Protocol Encryption, Quantum Inf. Process 15(5) Based on Permutations, IEEE 2nd Int. (2016) 2101–2111. doi: 10.1007/s11128- Conf. Adv. Trends Inf. Theory (2020) 016-1253-8. 281–284. doi: 10.1109/ATIT50783. [21] R. Mohajer, Z. Eslami, Cryptanalysis of a 2020.9349343.

Multiparty Quantum Key Agreement [31] H. Huang, C. Li, L. Deng, Public-Key Protocol Based on Commutative Encryp- Cryptography Based on Tropical Circular tion, Quantum Inf. Process 16(8) (2017). Matrices, Appl. Sci. 12(15) (2022). doi: doi: 10.1007/s11128-017-1647-2. 10.3390/app12157401. [22] S. Sihare, Dynamic Multi-Party Quantum [32] F. Dupont, A New Shamir’s Three Pass Key Agreement Protocol Based on Random Matrix Ciphering Mechanism, J. Commutative Encryption, Int. J. Theor. Comput. Virology Hacking Techniques, Physics 61(9) (2022). doi: (2023) 1–12. doi: 10.1007/s11416-02310.1007/s10773-022-05203-w. 00467-0. [23] E. Faure, et al., Permutation-Based Block [33] T. Springer, Linear Algebraic Groups, Code for Short Packet Communication Modern Birkhäuser Classic, 2nd ed.,

References

[1] A. Bessalov , et al., CSIKE-ENC Combined Encryption Scheme with Optimized Degrees of Isogeny Distribution , in: Workshop on Cybersecurity Providing in Information and Telecommunication Systems , vol. 3421 ( 2023 ) 36 - 45 .

[2] A. Bessalov , et al., Modeling CSIKE Algorithm on Non-Cyclic Edwards Curves , in: Workshop on Cybersecurity Providing in Information and Telecommunication Systems , vol. 3288 ( 2022 ) 1 - 10 .

[3] A. Bessalov , et al., Implementation of the CSIDH Algorithm Model on Supersingular Twisted and Quadratic Edwards Curves , in: Workshop on Cybersecurity Providing in Information and Telecommunication Systems , vol. 3187 , no. 1 ( 2022 ) 302 - 309 .

[4] A. Bessalov , et al., Implementation of the CSIDH Algorithm Model on Supersingular Twisted and Quadratic Edwards Curves , in: Workshop on Cybersecurity Providing in Information and Telecommunication Systems , vol. 3187 , no. 1 ( 2022 ) 302 - 309 .

[5] A. Bessalov , et al., Computing of Odd Degree Isogenies on Supersingular Twisted Edwards Curves, in: Workshop on Cybersecurity Providing in Information and Telecommunication Systems , vol. 2923 ( 2021 ) 1 - 11 .

[6] W. Diffie , M. Hellman , New Directions in Cryptography, IEEE Transactions on Information Theory 22 ( 6 ) ( 1976 ) 644 - 654 . doi: 10 .1109/TIT. 1976 . 1055638 .

[7] R. Rivest , A. Shamir , L. Adleman , A Method for Obtaining Digital Signatures and Public-Key Cryptosystems , Communications of the ACM 21 ( 2 ) ( 1978 ) 120 - 126 . doi: 10 .1145/359340. 359342.

[8] A. Shamir , R. Rivest , L. Adleman , Mental Poker, The Mathematical Gardner ( 1981 ) 37 - 43 . doi: 10 .1007/978-1- 4684 -6686- 7 _ 5 .

[9] J. Massey , J. Omura , Method and Apparatus for Maintaining the Privacy of Digital Messages Conveyed by Public Transmission ( 1986 ).

[10] P. Shor , Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer , SIAM J. Comput . 26 ( 5 ) ( 1997 ) 1484 - 1509 . doi: 10 .1137/S00975397952931 72.

[11] A. Moldovyan , D. Moldovyan , N. Moldovyan , Post-Quantum Commutative Encryption Algorithm , Comput. Sci. J. Moldova 81 ( 3 ) ( 2019 ) 299 - 317 . Berlin ( 1998 ). doi: 10 .1007/978-0- 8176 -4840-4.

[34] A. Baker , Matrix Groups . An Introduction to Lie Group Theory, Springer ( 2002 ). doi: 10 .1007/978-1- 4471 -0183-3.

[35] S. Lipschutz , Schaum's Outline of Theory and Problems of Linear Algebra , 2nd ed., McGraw-Hill , NY ( 1991 ).

[36] F. Gantmacher , The Theory of Matrices , Reprinted, American Mathematical Society , Providence, RI ( 1959 ).

[37] J. Laughlin , Combinatorial Identities Deriving from the n-th Power of a 2x2 Matrix, Integers 4 ( 2004 ) 1 - 15 . doi: 10 .48550/ARXIV. 1812 . 11168 .

[38] V. Arnold , Fermat Dynamics, Matrix Arithmetics, Finite Circles, and Finite Lobachevsky Planes, Functional Analysis Its Appl . 38 ( 1 ) ( 2004 ) 1 - 13 . doi: 10 .1023/B:FAIA. 0000024863 .06462.68.

[39] S. Wright , Quadratic Residues and NonResidues, Lecture Notes in Mathematics 2171 ( 2016 ). doi: 10 .1007/978-3- 319 - 45955-4.