Published: 09 May 2024

On the decisional problem based on matrix power function defined over non-commutative group

Aleksejus Mihalkovich1
Jokubas Zitkevicius2
1, 2Department of Applied Mathematics, Kaunas University of Technology, Kaunas, Lithuania
Corresponding Author:
Aleksejus Mihalkovich
Article in Press
Views 3
Reads 0
Downloads 21

Abstract

In this paper, we perform statistical analysis for the decisional problem which is fundamental for the security of the key exchange protocol based on matrix power function. We have proven previously that the considered decisional problem is NP-complete and hence our proposal could potentially be quantum-safe. However, we did not explore the dependence of the complexity of the considered problem on the security parameters. Here we show that for small matrices certain information could be gained from the distribution of the entries of the public key matrices. On the other hand, we show that as the size of the matrices grows, the public key matrices are indistinguishable from truly random matrices.

1. Introduction

A novel idea presented by W. Diffie and M. Hellman in [1] of using a pair of keys to agree on a shared secret gave birth to the branch of public-key cryptography. Since then, much research has been performed in this field and widely known cryptosystems such as RSA and many others were proposed. However, these cryptosystems mostly relied on the security of the discrete logarithm problem (DLP) defined in some multiplicative group (a version of DLP for additive groups e.g. elliptic curves can also be defined) or integer factorization problem [2]. While these problems do provide a decent challenge, due to the findings published by P. Shorr in [3] these problems could be solved by quantum computers.

For some time, quantum computers were viewed as a mostly theoretical threat. However, due to the rapid development of quantum technologies, by the mid-2010s quantum cryptanalysis could no longer be viewed as purely theoretic. In 2016 the National Institute of Standards and Technology (NIST) announced a call for post-quantum algorithms for standardization [4]. As of now the finalists of round 3 have been announced [5]. Furthermore, the development of quantum-safe cryptographic schemes continues due to the increasing practical demand of such algorithms in the near future.

The proposed cryptographic schemes rely on hard problems e.g. defined in lattices or using multivariate quadratic equations. Alternatively error correction codes, hash-based cryptography or elliptic curves isogenies could be used to construct quantum-safe algorithms [6,7]. The security of such algorithms relies on NP-hard computational problems, i.e. they are in the hardest class of problems which cannot be solved by a deterministic Turing machine in polynomial time. Moreover, decisional versions of some of these problems are known to be NP-complete, e.g. closest vector problem used in lattice-based cryptography [8]. It is widely believed that such problems can withstand quantum cryptanalysis.

In this paper, we consider one of such problems which is fundamental for the security of the cryptographic protocols presented in [9] and [10]. The objective of this problem is to recover the secret key of the legitimate user based on his public key [9]. Our goal is to show that the produced key is statistically indistinguishable from a truly random matrix if the public parameters of the protocol are appropriately chosen. We think that our results pose an interest from the practical implementation point of view, since the choice of the security parameters influences the memory requirements to store the private and public data and hence can be fundamental to determining if our proposal can be implemented in memory-restricted devices.

The rest of this paper is organized as follows: in Section 2 we revise the mathematical background of our research; in Section 3 we define the considered problem in the form of the security game and present the main results of this paper. As usual, conclusions are presented at the end of the paper.

2. Mathematical background

Our approach is related to multivariate cryptography. Specifically, we focus on a certain mapping called the matrix power function (MPF) first introduced in [11]. The idea of this mapping is somewhat similar to the classical matrix multiplication. However, since MPF is defined for matrices with entries chosen from multiplicative (semi)group S, we use multiplication as the operation in S and exponentiation as the scalar multiplication. Hence, we obtain the following expressions defining the one-sided MPFs [11]:

1
W X=A, aij=k=1mwkjxik,
2
WY=B, bij=k=1mwikxkj.

The matrix W in Eq. (1) and Eq. (2) is called the base matrix with its entries chosen from the multiplicative (semi)group S. We refer to S as the platform (semi)group. The matrices X and Y in Eq. (1) and Eq. (2) respectively are referred to as power matrices. Their entries are chosen from a ring of scalars ZordS, where ord(S) denotes the multiplicative order of S, i.e. the smallest natural number satisfying the relation wordS=e for any wS, and e is the identity of S.

In our early research related to MPF we considered various commuting platform groups [12–14]. It was shown in [12] that is this case MPF is associative, i.e. the following identity holds:

3
W XY=WY=W XY X.

Hence, we obtain the definition of the two-sided MPF. Unfortunately, our early proposals presented in [12] and [14] were attacked in [15] using tools of linear algebra together with discrete logarithm mapping. Though we fixed the flaw in our paper [16], and investigated this enhanced version in [17], partly due to the presented attack, our attention turned to non-commuting platform groups, where Eq. (3) does not hold in general, and hence the order of actions must be taken into consideration. In [9] and [18] we have shown that we can define hard decisional problems based on MPF defined over non-commuting platform groups thus demonstrating that MPF is a possible candidate for the so-called one-way function – easy to calculate, hard to invert.

In this paper, we consider a family of the so-called modular-maximal cyclic groups generally denoted by M2t and defined as follows [19-21]:

4
M2t=a,b|a2t-1=e, b2=e,bab-1=a2t-2+1,

where a and b are two non-commuting generators of the group and e is the identity of the group. Note that the parameter t defines the size of M2t, i.e. M2t=2t, and hence we refer to it as the group-defining parameter. All the elements of M2t can be represented in two ways: either aαbβ or bβaα, where αZ2t-1 and β Z2. Since both these representations are equivalent, in this paper, we use the representation aαbβ for the elements of M2t.

Basic operations in this group are presented below [9].

Multiplication of two elements:

5
aα1bβ1aα2bβ2=aα1+α2bβ2, β1=0,aα1+α2b1+β2, β1=1, α2 is even,aα1+α2+2t-2b1+β2, β1=1, α2 is odd.

Exponentiation to the power k:

6
aαbβk=akα, β=0,akαbk, β=1, α2 is even,akα+2t-2k2b1+β2, β=1, α2 is odd.

An important corollary of these expressions is the fact that there are two cyclic subgroups of M2t of size 2t-1. These subgroups are generated by elements a and ab. We denote them by a and ab respectively. Their explicit presentations are given below:

7
a=e, a, a2,,a2t-1-1,
8
ab=e, ab, a2,a3b,,a2t-1-1b.

It is important to note that in general elements from a and ab do not commute. This fact plays a major role in the application of M2t in our research. Specifically, we defined the form of the base matrix W as well as the forms of the secret key matrices.

Template 1. The base matrix W is chosen randomly to fit the following form [9]:

9
W=a2k11+1bak12a2kc1+lc1blc1ak1(m-1)a2k1m+1ba2k21ak22a2kc2+lc2blc2ak2(m-1)a2k2ma2km1+1bakm2a2kcm+lcmblcmakm(m-1)a2kmm+1b.

The main idea behind this template is to choose the entries of the columns in such a way that in each of the individual column entries are in the same cyclic subgroup either a or ab. This way we ensure that each individual column contains commuting entries. However, we still have to make sure that the exponentiation from the right is also performed with commuting entries. To achieve this goal, we define the following templates for power matrices [9]:

Template 2. The left power matrix X is chosen at random to satisfy the following condition:

10
xi1+xim0 mod 2.

Template 3. The right power matrix Y is chosen at random to satisfy the following condition:

11
ycj0 mod 2.

Previously in [9] we proposed a key exchange protocol where we used M2t as a platform group for the MPF with similar templates for matrices. Also, using the ideas presented in that paper we proposed a sigma identification protocol in [10]. Here we focus on these ideas presented in a more general way, i.e. we consider the MPF with additional constraints given by the Templates 1, 2 and 3 defined above to keep the results obtained here applicable for future research in this area.

3. Decisional problem based on MPF

In this section we consider the following security game aimed at distinguishing an MPF value from a truly random matrix:

Security Game. Let W be a matrix satisfying Template 1. For a given adversary A and its challenger C we define the following game:

1) C chooses at random two matrices X and Y satisfying Templates 2 and 3 respectively and computes K0=W XY.

2) C generates a random matrix K1 with entries k1ijZ2t-1.

3) C gives the pair W,Kβ, where β{0,1} to A.

4) A outputs β^.

The adversary A wins the game if β^=β.

To put it simpler, the aim of the game is to answer YES/NO to the following question: is there a pair of matrices X,Y satisfying Templates 2 and 3 respectively, such that Kβ= W XY. Hence, we obtain a decisional problem based on MPF defined over a non-commutative platform group. Here we refer to this problem as MPF decisional problem.

Previously in [9] we used Schaefer’s dichotomy theorem to show that a special case of this problem when matrices X and Y are generated as polynomials of pre-fixed matrices L and R with coefficients from Z2t-1 is NP-complete. However, we did not explore the dependence of the complexity of this problem on the order of the matrices or the size of the platform group M2t. Here we focus on these dependencies, i.e. we are interested in determining how difficult it is to solve the considered decisional problem for distinct values of the group size-defining parameter t and the matrix order m.

Our results are based on the statistical analysis of the distribution of the entries of the MPF value matrix K0. Our goal is to show that the entries of K0 are distributed uniformly in Z2t-1 as a truly random matrix K1 has uniformly distributed entries.

The statistical analysis was performed as follows:

1) We generate a matrix W that satisfies Template 1.

2) We select a natural number k that defines the total number of iterations executed.

3) Within the l-th iteration, where 1lk, a new pair of matrices Xl,Yl is generated such that the matrix Xl satisfies Template 2 and the matrix Yl satisfies Template 3. For each pair we calculate the matrix exponent Vl=W XlYl.

4) We store the frequencies of powers of the generator a two different ways: an array q stores the overall frequencies of powers, and a tensor Q keeps track of frequencies in each individual position in the matrix exponent, i.e. we obtain m2 separate samples, where m is the size of the matrices. Denote by fz, Vl the frequency of the element az in the matrix exponent Vl and denote by fij(z,Vl) the frequency of the element az in the i,j-th position of matrix exponent Vl. Then we have:

12
q=l=1kf0, Vll=1kf1, Vll=1kf2t-1-1, Vl,
13
Q=q11q1mqm1qmm, qij=l=1kfij0, Vll=1kfij2t-1-1, Vl.

5) After all k iterations have been executed, we perform Pierson chi-squared test for uniform distribution for q and each sample qijQ separately at a 0.05 significance level and calculate p-value for all of the obtained values of the chi-squared statistics.

If the null hypothesis is rejected for the sample q, then there may exist patterns in the structure of the key matrix K0 distinguishing it from a truly random matrix, i.e. some values of K0 might be more likely than others. Hence an adversary has a non-negligible chance of winning the security game defined above. Moreover, if the null hypothesis is rejected for multiple samples qij of the tensor Q then there is a potential threat of pattens for some individual positions and the adversary may use this partial information leak to win the considered security game with non-negligible probability, if these patterns are stable under repeats of the experiment.

Let us consider an example of the performed experiment consisting of k= 1000 iterations. Assume the parameter values t=4 and m=8. The following base matrix W was generated:

14
W=a3ba3a4aea7a5a5ba4a4a6a5a7ba5a7a6a2aaa5ea2aa2a4a2a2a5eea4a2a4ea6a7aba4a6a6a6ea7a5ea7a5a2a6a7eaa6a2a7a6a3ba5aa3aba2a3a5b.

Note that for this choice of W we have c=5 in Eq. (11).

Since there are a total of 1000 pairs (Xi,Yi) generated and matrix exponents Vi calculated, here we present only the matrices obtained during the first iteration as the example:

15
X1=1023612740243446634631120475713471665245506613210336427414454261, Y1=3544121473471221127251004714210746422220107250000171000001030365,
V1=ea7a3aa6a4eeea5aa4a4a5ea3a4a6a2a2a6a3a2a7a5a2aa7aa7ea7a3a7a6a3aa7a2a4ea3a7a3a4ea4a2eea6a7a4a4a2aa2aa5a2a6a4a4a7.

The histogram after 1000 iterations is presented below. Also, for comparison we have generated 1000 random matrices with entries uniformly chosen from Z8.

Due to the low p-value of the obtained results the null hypothesis is rejected in case of Fig. 1(a) and hence the tensor Q was not considered. We could explain this result by inspecting the elements of the given W: since in the first and last columns even-degree powers must dominate due to Template 1 and we only have 8 columns in total, the impact of even powers is crucial when exponentiating to left and right power matrices in Eq. (1) and Eq. (2) respectively. Hence, we see that the even powers of the generator a are more likely in this case.

After performing a couple of extra experiments with the same parameters, the p-value did not increase, so we assume that repeating the experiment does not significantly change the p-value. Hence, relying on the obtained results we see that the MPF decisional problem is solvable for this case. In other words, due to the observed pattern of the even powers being more frequent, we see a significant difference between the MPF value K0 and a truly random matrix K1 as presented in Fig. 1. Hence, the matrix order is too small to obtain a complex MPF decisional problem.

On the other hand, based on the presented results we make a conjecture that the observed parity effect becomes less noticeable or even disappears as the size of the matrix increases, since the matrix W contains more free columns and the impact of the three specific columns reduces.

Fig. 1Comparison of the results of the experiment to truly random data for security parameters t=4 and m=8

Comparison of the results of the experiment to truly random data  for security parameters t=4 and m=8

a) Histogram for the experiment data: p-value for sample q: 3.5⋅10-15

Comparison of the results of the experiment to truly random data  for security parameters t=4 and m=8

b) Histogram for truly random matrices: p-value for sample q: 0.60

Let us now present our findings for the parameter values: t=4 and m=12. The idea of the experiment stays the same and the total number of iterations is k= 1000. We suppress the explicit presentation of the matrix W to shorten the paper. For better comparison we repeat the experiment three times each time changing the matrix W. Also, we have generated 1000 truly random 12×12 matrices. The results are presented in Fig. 2.

Evidently, the p-values differ in all cases, but all of them are greater than the selected threshold of 0.05. Interestingly enough, the p-value of the truly random data was less than the p-value of the Experiment 3 and comparable to other obtained p-values. Moreover, we can see that even for truly random data the null hypothesis was rejected for several positions of the matrix. However, there are no recognizable patterns in the positions where the uniformness was rejected. Neither the number of such positions nor their locations in the matrices are stable. Hence the adversary cannot acquire any valuable information by studying these positions which could potentially increase the probability of winning the considered security game. Relying on these observations we claim that for these parameter values the MPF value K0 is indistinguishable from a truly random matrix K1.

Additionally, we performed experiments with other values of the security parameters. Since p-values for the experiments greatly vary and sometimes become lower than the considered threshold. For this reason, for each platform group M16, M32, M64 and M128 we performed the search for the smallest m such that the null hypothesis could not be rejected for all the experiments. We started at 8×8 matrices and increased m by 1 until all 25 experiments produced p-values greater than 0.05. Based on the obtained results we make a conjecture that considered security game could not be won in the average case for the following parameter values shown in Table 1.

Table 1Minimal matrix size dependence on the platform group

Platform group
M16
M32
M64
M128
m
14
14
14
> 16

We can see from the presented results that as the cardinality of the platform group increases, the impact of even degrees becomes more noticeable. Hence, for practical implementation of our KEP it may be reasonable to consider a balance between the cardinality of the platform group and the matrix size, since large matrices require more available memory space. For example, for the platform group M16 and 14×14 matrices 490 bytes of memory are needed to store matrices W, L, R, X, Y and A, whereas for the platform group M128 and 16×16 matrices 1216 bytes of memory are required to store this data and the protocol is potentially less secure in the statistical sense. Also, memory is required to store a vector of coefficients. Moreover, it may be a good idea to store tables for mathematical operations in the platform group as well as powers of L and R to speed up the execution of the protocol in exchange for memory.

Fig. 2Comparison of the results of the experiment to truly random data for security parameters t= 4 and m= 12

Comparison of the results of the experiment to truly random data  for security parameters t= 4 and m= 12

a) Experiment 1: p-value for sample q: 0.15; H0 rejected for the following positions of Q: 2,9, 4,6, 5,7, 6,6, 6,10, 6,12, 7,12, (12,5)

Comparison of the results of the experiment to truly random data  for security parameters t= 4 and m= 12

b) Experiment 2: p-value for sample q: 0.09; H0 rejected for the following positions of Q: 2,4, 3,9, 5,7, 7,9, 11,12

Comparison of the results of the experiment to truly random data  for security parameters t= 4 and m= 12

c) Experiment 3: p-value for sample q: 0.37; H0 rejected for the following positions of Q: 1,9, 4,8, 4,9, 4,10, 6,3, 8,1, 8,10, 10,9, 11,4, 11,6, 12,3, (12,10)

Comparison of the results of the experiment to truly random data  for security parameters t= 4 and m= 12

d) Truly random matrices: p-value for sample q: 0.16; H0 rejected for the following positions of Q: 1,11, 1,12, 2,1, 2,5, 6,11

In conclusion we note that due to the sporadic changes of the p-value the obtained results should be viewed as recommendations based purely on statistical results. In other words, these result must be viewed as minimal recommendations for the values of public parameters. Algebraic analysis must also be taken into consideration. Such methods as the linearization technique, or the faithful matrix representation of the elements of the group M2t were not considered in this work. Should these methods provide the adversary with some useful information about private keys, we must evaluate the dangers caused by them and hopefully avoid them by appropriately increasing the values the public parameters of the system.

4. Conclusions

In this paper, we have presented the results of the statistical analysis aimed at distinguishing the public key of the legit user from a truly random matrix. We have shown that for small matrices the adversary can gain a significant advantage in winning the security game defined in Section 3 based on the distribution of the entries of the public key matrix. However, this advantage vanishes as matrices become larger. Hence, based on the presented results we could recommend considering matrices of size 14 at the very least. Additional experiments are needed to find the optimal size of matrices for large groups, i.e. when the group-defining parameter t7.

Notably, the security of our protocol relies on a hard decisional problem. However, the latter result means that to implement our protocol in practice, we need to find the balance between the choice of public parameter values and the required memory for data storage. Furthermore, unreasonably large values of the public parameters can also negatively affect the execution time of the protocol thus making it less attractive to the designers of cryptographic software.

The obtained results will serve as a basis for our future research of other cryptographic primitives based on the MPF defined over modular-maximal cyclic groups.

References

  • W. Diffie and M. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, Vol. 22, No. 6, pp. 644–654, Nov. 1976, https://doi.org/10.1109/tit.1976.1055638
  • D. Boneh and V. A. Shoup, Graduate Course in Applied Cryptography. 2020.
  • P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in 35th Annual Symposium on Foundations of Computer Science, pp. 124–134, Apr. 2024, https://doi.org/10.1109/sfcs.1994.365700
  • “Post-Quantum Cryptography,” Computer Security Division, https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/call-for-proposals
  • “NIST Announces First Four Quantum-Resistant Cryptographic Algorithms,” NIST, 2022.
  • D. J. Bernstein and T. Lange, “Post-quantum cryptography,” Nature, Vol. 549, No. 7671, pp. 188–194, Sep. 2017, https://doi.org/10.1038/nature23461
  • R. Badhwar, “The need for post-quantum cryptography,” in The CISO’s Next Frontier, Cham: Springer International Publishing, 2021, pp. 15–30, https://doi.org/10.1007/978-3-030-75354-2_2
  • D. Micciancio and S. Goldwasser, Complexity of Lattice Problems. Boston, MA: Springer US, 2002, https://doi.org/10.1007/978-1-4615-0897-7
  • A. Mihalkovich, E. Sakalauskas, and K. Luksys, “Key exchange protocol defined over a non-commuting group based on an NP-complete decisional problem,” Symmetry, Vol. 12, No. 9, p. 1389, Aug. 2020, https://doi.org/10.3390/sym12091389
  • A. Mihalkovich, K. Luksys, and E. Sakalauskas, “Sigma identification protocol construction based on MPF defined over non-commuting platform group,” Mathematics, Vol. 10, No. 15, p. 2649, Jul. 2022, https://doi.org/10.3390/math10152649
  • E. Sakalauskas and K. Luksys, “Matrix power S-box construction,” Cryptology ePrint Archive, 2007.
  • E. Sakalauskas, N. Listopadskis, and P. Tvarijonas, “Key agreement protocol (KAP) based on matrix power function,” in 6th International Conference on Information Research and Applications, 2008.
  • A. Mihalkovič and E. Sakalauskas, “Asymmetric cipher based on MPF and its security parameters evaluation,” Proceedings of The Lithuanian Mathematical Society, Vol. 53, pp. 72–77, 2012.
  • E. Sakalauskas and A. Mihalkovich, “New asymmetric cipher of non-commuting cryptography class based on matrix power function,” Informatica, Vol. 25, pp. 283–298, 2014.
  • J. Liu, H. Zhang, and J. Jia, “A linear algebra attack on the non-commuting cryptography class based on matrix power function,” in Information Security and Cryptology, pp. 343–354, Mar. 2017, https://doi.org/10.1007/978-3-319-54705-3_21
  • E. Sakalauskas, A. Mihalkovich, and A. Venčkauskas, “Improved asymmetric cipher based on matrix power function with provable security,” Symmetry, Vol. 9, No. 1, Jan. 2017, https://doi.org/10.3390/sym9010009
  • A. Mihalkovich and M. Levinskas, “Investigation of matrix power asymmetric cipher resistant to linear algebra attack,” in Information and Software Technologies, pp. 197–208, Oct. 2019, https://doi.org/10.1007/978-3-030-30275-7_16
  • E. Sakalauskas and A. Mihalkovich, “MPF problem over modified medial semigroup is NP-complete,” Symmetry, Vol. 10, No. 11, p. 571, Nov. 2018, https://doi.org/10.3390/sym10110571
  • H. Grundman and T. Smith, “Automatic realizability of Galois groups of order 16,” Proceedings of the American Mathematical Society, Vol. 124, No. 9, pp. 2631–2640, Jan. 1996, https://doi.org/10.1090/s0002-9939-96-03345-x
  • H. G. Grundman and T. L. Smith, “Realizability and automatic realizability of Galois groups of order 32,” Central European Journal of Mathematics, Vol. 8, No. 2, pp. 244–260, Apr. 2010, https://doi.org/10.2478/s11533-009-0072-x
  • H. G. Grundman and T. L. Smith, “Galois realizability of groups of order 64,” Central European Journal of Mathematics, Vol. 8, No. 5, pp. 846–854, Aug. 2010, https://doi.org/10.2478/s11533-010-0052-1

About this article

Received
11 March 2024
Accepted
11 April 2024
Published
09 May 2024
Keywords
non-commuting cryptography
statistical cryptanalysis
uniform distribution
Acknowledgements

The authors have not disclosed any funding.

Data Availability

The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.

Author Contributions

Aleksejus Mihalkovich: conceptualization, formal analysis, investigation, methodology, project administration, supervision, writing and visualization. Jokubas Zitkevicius: data curation, formal analysis, investigation, software, writing and visualization.

Conflict of interest

The authors declare that they have no conflict of interest.