access icon free Key recovery on several matrix public-key encryption schemes

© The Institution of Engineering and Technology
Received 14/10/2014, Accepted 03/08/2015, Revised 30/07/2015, Published 01/05/2016

Eight years ago, Pei et al. described a matrix public-key encryption scheme based on the matrix factorisation over a finite field. Recently, Gu and Zheng also proposed a similar scheme based on the non-abelian factorisation assumption. The security of these schemes is essentially based on a two-side matrices exponentiation (TSME) problem. In this study, the authors show that the TSME problem is susceptible to a very efficient linearisation equations attack. Regardless of the public key parameters, the authors can easily find an equivalent key only in polynomial time 𝒪(2n 5(log n +1)) from the public key alone, and thus it is very practical and can be implemented within less than 1/20 of a second on the recommended system parameters of the schemes.

Inspec keywords: public key cryptography; matrix decomposition; linearisation techniques

Other keywords: polynomial time; matrix public-key encryption schemes; TSME problem; public key parameters; linearisation equation attack; two-side matrix exponentiation problem; key recovery; matrix factorisation; nonabelian factorisation assumption

Subjects: Data security; Cryptography theory; Algebra; Algebra; Cryptography

References

    1. 1)
      • 8. Bernstein, D., Buchmann, J., Dahmen, E.: ‘Post-quantum cryptography’ (Springer-Verlag, Berlin, 2009).
    2. 2)
      • 9. Ding, J., Gower, J., Schmidt, D.: ‘Multivariate public key cryptosystems’ (Springer-Verlag, 2006, 1st edn.).
    3. 3)
      • 5. Gu, L., Zheng, S.: ‘Conjugacy systems based on nonabelian factorization problems and their applications in cryptography’, J. Appl. Math., 2014, 6, pp. 1–10.
    4. 4)
      • 12. Matsumoto, T., Imai, H.: ‘Public quadratic polynomial-tuples for efficient signature verification and message encryption’. Proc. Int. Conf. Cryptology-Eurocrypt, Davos, Switzerland, May 1988, pp. 419–453.
    5. 5)
      • 7. Okamoto, T., Tanaka, K., Uchiyama, S.: ‘Quantum public-key cryptosystems’. Proc. Int. Conf. Crypto, California, USA, August 2000, pp. 147–165.
    6. 6)
      • 4. Pei, S., Zhao, Y., Zhao, H.: ‘Public key encryption scheme based on the ergodic matrices’, Chinese J. Electron., 2010, 38, (8), pp. 1908–1913.
    7. 7)
    8. 8)
      • 6. Gu, C., Yu, Z., Jing, Z., et al: ‘Cryptanalysis on public key encryption scheme using ergodic matrices over GF(2)’. Proc. Int. Conf. Artificial Intelligence and Symbolic Computation, April 2012, pp. 129–135.
    9. 9)
      • 3. Pei, S., Zhao, Y., Zhao, H.: ‘Construct public key encryption scheme using ergodic matrices over GF(2)’. Proc. Int. Conf. Theory and Applications of Models of Computation, Shanghai, China, May 2007, pp. 181–188.
    10. 10)
      • 10. Kipnis, A., Shamir, A.: ‘Cryptanalysis of the HFE public key cryptosystem by relinearization’. Proc. Int. Conf. Cryptology, California, USA, August 1999, pp. 19–30.
    11. 11)
      • 13. Patarin, J.: ‘Cryptanalysis of the matsumoto and imai public key scheme of eurocrypt 1988’. Proc. Int. Conf. Cryptology, California, USA, August 1995, pp. 248–261.
    12. 12)
      • 11. Zhao, Y., Zhao, B., Pei, S.: ‘On the properties of the ergodic matrix over finite field’, ACTA MATHEMATICA SINICA (Chinese Series), 2012, 55, (3), pp. 457–468.
    13. 13)
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0183
Loading

Related content

content/journals/10.1049/iet-ifs.2015.0183
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading