Cryptanalysis of a Cryptosystem with Non-Commutative Platform Groups

Jinhui Liu, Jianwei Jia, Huanguo Zhang, Rongwei Yu,*, Yong Yu, Wangqing Wu College of Computer Science, Shaanxi Normal University, Xi’an, Shanxi, China Computer School of Wuhan University, Wuhan, Hubei, China Key Laboratory of Aerospace Information security and trusted computing Ministry of Education, Wuhan University, Wuhan, Hubei, China School of Computer Science and Technology, Hebei University, Baoding, China

I. INTRODUCTION

Most public-key cryptosystems used today rely on the hardness of either factoring or computing discrete logarithms. However,the trustworthiness of these assumptions has been eroding by improvements in factoring algorithms and by polynomial time quantum algorithms that solve both problems. These are some reasons which motivate researchers to develop a new family of cryptosystems that can resist quantum computers attacks and that are more efficient in terms of computation. In recent years, cryptographers have been making efforts in the area of post-quantum computational cryptography [1-9]. People also began to construct some alternative post-quantum(i.e., quantum-resistant) public key cryptosystems from other mathematically intractable problems [10-15].

Before going into details we would like to mention that nonabelian algebraic structures has already been used in a cryptographic context. For a general introduction we refer to [8, 9, 16]. During the last decades, many public key cryptosystems based on non-abelian algebraic structures were proposed, such as cryptosytems based on inner automorphism groups, general linear groups and braid groups[3, 8, 17]. However, this area is immature and there are few practical non-commutative cryptosystems in efficiency and security at present[18, 19, 20, 21].

The main contribution of this paper is that we present an algebraic key-recovery attack able to break a cryptosystem with noncommutative platform groups which was proposed on Neural Computing and Applications 2016[22].For the scheme, the time complexity is both dominated by the need to compute homoge-neous linear equations, which can be evaluated by basic linear operations. We peel off an encryption and decryption process and propose attack method for solving the cryptosystem over matrix groups. Finally, we provide corresponding examples to illustrate the attack methods in our cryptanalysis.

The remainder of this paper is organized as follows. Section 2 reviews the necessary material as background to this work. Section 3 provides an overview of a cryptosystem with noncommutative platform groups. Section 4 presents our main attack, and shows the corresponding description and efficiency analysis.In Section 5, the computational complexity and practical attack of the scheme are proposed. Lastly, Section 6 provides some concluding remarks and discusses possible lines of future work.

II. PRELIMINARIES

Throughout this paper, we use the following notations.

q: a power of prime;

Fq: a finite field of orderq;

For an integerk≥1,

GLk(Fq): the set ofk×kinvertible matrices of Fqentries;

Mk(Fq): the set ofk×kmatrices of Fqentries;

Ikthe identity matrix.

The public key is

For a matrix A,

AT: the transpose of A.

Proposition 1.The Kronecker product ⊗has the following simple properties:

Proposition 2:Stacking the row of a matrix into one long row vectorhas the following simple properties:

Definition 1. (Discrete Log Problem,DLP)[14] Suppose thatGis a finite cyclic group generated byg. Givengandh=gkinG, the problem of finding an integerkis known as discrete log problem.

Definition 2. (Conjugator Search Problem, CSP)[14] Suppose thatGis a finite cyclic group. GiveninG, the problem of determining the conjugatorx∈Gis known as conjugator search problem .

III. DESCRIPTION OF THE PUBLIC KEY CRYPTOSYSTEM

KeyGen:Choose a noncommutative groupGhaving the elements with large orders. Leta,b∈Gsatisfyingab≠baandn1be the order of the elementaandn2be the order of the elementb. Alice randomly chooses two natural numbersrandswith 0＜r＜n1and 0＜s＜n2. Then, she computesKA=arbs.and the secret key issk=(r,s)

Enc(m,pk): To send a plaintextm∈Gto Alice, he inputs the public keypkand the messagem.Bob choosesvandwwith 0＜v＜n1, 0＜w＜n2randomly and calculate

Output a ciphertext pair (C,C′).

Dec(C,sk): Alice receives the ciphertext,then she inputs the private keyskand the ciphertextCand computes

In the following section, we show that the proposed cryptosystem based on CSPdo not provide security.

IV. KEY RECOVERY ATTACK

According to the construction of the cryptosystems based onCSP,we simply need to show that an adversaryAcould obtain the message of the encryption scheme. Because of adversaryA’s ability to use the public keyand the ciphertext (C,C′),where

He or she could obtain the legal message through the following process. A solves two invertible elementsp,qsatisfying the following system:

From the above, If an adversary can find a pair of (p,q) satisfied the Eq.(1), then the proposed cryptosystem based on CSP can be broken.

V. COMPUTATIONAL COMPLEXITY AND PRACTICAL ATTACK ON PUBLIC KEY CRYPTOSYSTEM BASED ON CSP

In this section, for a matrix group G overZkin [22], our goal is to recover the equivalent private key of the legal message, using only the public key. For this purpose, we peel off the encryption and decryption process and propose attack ways to explain our key recovery attack. Then we provide corresponding examples to illustrate the attack methods in our cryptanalysis.

p,q are two inversen×nmatrices, and equation(1) is to solve linear equations in the following:

By Proposition 2, the Eq.(1) is equivalent to solving the following linear equations:

where are the stretches of the matrices p respectively, ⊗ represents the Kronecker product, I is then×nidentity, 0 is the matrix with all-zero elements.

Proposition 3:The cryptosystem can be broken for all given public keys.

Proof:Obviously avis one of the solutions of the Eq.(4), we can guarantee the existence of solutions for Eq.(4), which indicates the existence of solutions for Eq.(1). Finally we could proof this proposition by using section 4.

5.1 Algorithmic description and efficiency analysis

The method for recovery the plaintext m is shown in Algorithm 1. It takes as input the public keyand the ciphertext (C,C′) and outputs the plaintext m.

Algorithm 1:Recovering the plaintext m

step1:Input

step2:Solve nonhomogeneous linear equations in then2entries ofby Eq(4);

step3:Transform vectors p→ to matrices p;

step4: Compute

Step5:Return m.

Then, it remains to analyze the complexity of Algorithm 1, which can be concluded in the following.

To generate one random element p, one can take a linear combination of a basis of the solution space respectively. The number of free variables of the matrix Eq.(4) aren2-r,then the total expected running time of step 1 is about.Combining the above discussions, let us make a performance evaluation on Algorithm 1. The classical techniques for matrix multiplication inversion in Fqtake aboutbit operations,since the best known algorithm for the product of twon×nmatrices requiresO(nω)Fqoperations whereω≈2.3755 and each Fqoperation needs aboutbit operations[18, 22, 23]. Now, if we neglect small constant factors, the bit complexity of the Algorithm 1 is aboutBreaking a cryptosystem with noncommutative platform groups can be completed with a complexity of

5.2 Practical attack

In the following, we provide a practical attack example to illustrate the attack methods by using the toy example in [22]. The platform group is a general linear group of matrices of order 2 over F107.

Initial setup:

Key generation:Alice randomly chooses two natural numbersr=15,s=21 and computes

Bob randomly choosesv=37,w=51, then forms

where the message (plaintext)

The transmitted ciphertext is (C,C′).

Decryption:Alice computes

where

Now we illustrate the attack processes. We can obtain the informationand solve two invertible matrices p,q satisfying the following system

and

can be obtained by using equivalent private keys.

5.3 Experiments

We carry out our experiments on a 3.30 GHz Intel processor PC using the Magma implementation with different parameters for Algorithm 1 and then collect the results of our analysis in Table 1, where the notation “s” denotes seconds.

Through Table 1, it is clear that computation cost of Algorithm 1 is very low. Then whenn=5 is fixed, we list the time cost of Algorithm 1 in Figure 1. Finally, we provide the time cost of Algorithm 1 in Figure 2 whenq=220

It can be seen from Figure 1 and Figure 2 that the time of attack on designed security parameters is not big, which means that the scheme can be broken easily.

VI. CONCLUSIONS

We have showed that encryption propose on Neural Computing and Applications is insecure in the sense that an attacker, who is able to solve the linear equations with high efficiency in finite fieldsFq, is able to break the encryption schemes. The question as to whether there exists other groups on which the cryptosystem with noncommutative platform groups would be secure, remains open. When designing a cryptosystem with non-commutative platform groups for other groups the considerations of the previous section would have to be taken into account. The use of several non-abelian algebraic structures to construct a public key cryptosystem with the potential to resist attacks by known quantum algorithms,also remains open.

ACKNOWLEDGEMENTS

This work is supported by the State Key Program of National Natural Science of Chi-na(Grant Nos. 61332019), the National Natural Science Foundation of China (61572303),National Key Research and Development Program of China(2017YFB0802003,2017YFB0802004), National Cryptography Development Fund during the 13th Five-year Plan Period (MMJJ20170216), the Foundation of State Key Laboratory of Information Security (2017-MS-03) and the Fundamental Research Funds for the Central Universities(GK201702004,GK201603084), Major State Basic Research Development Program of China (973 Program) (No.2014CB340600),National High-tech R&D Program of China(2015AA016002, 2015AA016004). Natural Science Foundation of HeBei Province (No.F2017201199), and Science and technology research project of Hebei higher education(No. QN2017020)

Table I. Complexity of the algorithm 1.

Fig. 1. Attack time of algorithm 1

Fig. 2. Attack time of algorithm 1.

[1] NITAJ A. Post quantum cryptography[J]. Moulay Ismal niversity Faculty of Sciences and Technology of Errachidia epartment of Mathematics,2017, pp.7.

[2] Cheng C, Lu R, Petzoldt A, et al. “Securing the Internet of Things in a Quantum World”. IEEE Communications Magazine, vol. 55, no. 2, 2017,pp. 116-120.

[3] Takagi T., Post-Quantum Cryptography. Proc.Of PQCrypto 2016, Fukuoka, Japan, 2016, pp.1-245.

[4] Wu W Q, Zhang H G, Wang H Z, et al. “A public key cryptosystem based on data complexity under quantum environment”, Science China Information Sciences, vol. 58, no. 11, 2015, pp.1-11.

[5] Mosca, M. Post-Quantum Cryptography. Proc of PQCrypto 2013, Limoges, France, 2013, pp.1-122 .

[6] Zhang HG, Han WB, Lai XJ, et al., “Survey on cyberspace security”, Science China Information Sciences, vol. 58, no. 110101, 2016, pp. 1-43.

[7] Armknecht, F., Gagliardoni, T., Katzenbeisser,S.,Peter, A.“General impossibility of group homomorphic encryption in the quantum world”Proc. of Public Key Cryptography 2014, Buenos Aires, Argentina, 2014, pp. 556-573.

[8] Boaz Tsaban, “Polynomial-Time Solutions of Computational Problems in Noncommutative Algebraic Cryptography”. Journal of Cryptology,vol. 28, no. 3, 2015, pp. 601-622.

[9] ZHAO Guosheng, WANG Jian, “Security Analysis and Enhanced Design of a Dynamic Block Cipher”. China Communications, vol.13,no.1,pp.150-160,2016

[10] Mao SW, Zhang HG,Wu WQ,et al., “A Resistant Quantum Key Exchange Protocol and Its Corresponding Encryption Scheme”. China Communications, vol. 11, no. 9, 2014, pp. 131-141.

[11] Wang HZ, Zhang HG, Wang ZY, et al., “Extended multivariate public key cryptosystems with secure encryption function”. Science China Information Sciences, vol. 54, no. 6, 2011, pp. 1161-1171.

[12] San Ling, Duong Hieu Phan, Damien Stehl´e, et al.,“Hardness of k-LWE and Applications in Traitor Tracing”. Proc of crypto 2014, Santa Barbara,CA, USA, 2014, pp. 315-334.

[13] Regev O. “On lattices, learning with errors, random linear codes, and cryptography”. Proc of the ACM Symposium on Theory of Computing.New York, 2005, pp. 84-93.

[14] Micheli, Giacomo. “Cryptanalysis of a noncommutative key exchange protocol”, Advances in Mathematics of Communications, vol. 9, no. 2,2015, pp. 247-253.

[15] Albrecht M R, Faugere J C, Fitzpatrick R, et al.“Practical cryptanalysis of a public-key encryption scheme based on new multivariate quadratic assumptions”. Proc of PKC 2014, Buenos Aires, Argentina, 2014, pp. 446-464.

[16] Liu JH, Zhang HG, Jia JW, et al., “Cryptoanalysis of HKKS key exchange protocols”, Chinese Journal of Computers, vol. 39, no. 3, 2016, pp. 516-528.

[17] Habeeb, M., Kahrobaei, D., Koupparis, C., Shpilrain,V.“Public key exchange using semidirect product of (semi)groups”. Proc of ACNS 2013,Banff, AB, Canada, 2013, pp. 475-486.

[18] Liu JH, Zhang HG, Jia JW, et al., “Cryptanalysis of an asymmetric cipher protocol using a matrix decomposition problem”, Science China Information Sciencs, vol. 59, no. 5, 2016, pp. 1-11.

[19] Jia J, Liu J, Zhang H. “Cryptanalysis of cryptosystems based on general linear group”. China Communications, vol. 13, no. 6, 2016, pp. 217-224.

[20] Tsaban B. “Polynomial-time solutions of computational problems in noncommutative algebraic cryptography”. Journal of Cryptology, vol. 28,no. 3, 2015, pp. 601-622.

[21] Liu J, Fan A, Jia J, et al. “Cryptanalysis of public key cryptosystems based on non- Abelian factorization problems”. Tsinghua Science and Technology, vol. 21, no. 3, 2016, pp. 344-351.

[22] Kanwal S, Ali R. “A cryptosystem with non-commutative platform groups”. Neural Computing and Applications, 2016, pp. 1-6.

[23] Gashkov S B, Sergeev I S. “Complexity of computation in finite fields”, Journal of Mathematical Sciences, vol. 191, no. 5, 2013, pp. 661-685.