Structural Key Recovery of Simple Matrix Encryption Scheme Family. (29th September 2018)

• Record Type: Journal Article
• Authors: Liu, Jinhui; Yu, Yong; Yang, Bo; Jia, Jianwei; Wang, Shijia; Wang, Houzhen
• Editors: Martin, Keith
• Is Part Of: Computer journal. Volume 61:Number 12(2018)
• Page Start: 1880
• Page End: 1896
• Publication Date: 2018-09-29
• Subjects: post-quantum cryptography -- multivariate public-key cryptosystem -- linearization equations attack -- linear equations solving -- computational complexity; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy093
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Advances in quantum computers threaten the security of public-key cryptosystems whose security is based on the hardness of factoring or on the discrete logarithm problem. Multivariate encryption schemes are promising alternatives to traditional cryptosystems. Tao et al. proposed a new Multivariate Public-Key Cryptosystem for encryption called simple matrix encryption scheme (ABC for short). Further, they proposed an improved simple matrix encryption schemes and a cubic simple matrix encryption scheme. In this paper, we show that the three schemes are vulnerable to a structural key recovery attack by tensor and vectorization notation and associated algebraic re-writing rules. We derive a set of linear equations from the public key whose solution yields an equivalent key pair that hide the central map. The proposed cryptanalysis approaches require polynomial computational complexity to achieve some equivalent keys from associated public keys. In addition, we provide an example to illustrate feasibility of proposed analysis method.