Cryptology ePrint Archive: Report 2016/1075

Cryptanalysis of Simple Matrix Scheme for Encryption

Chunsheng Gu

Abstract: Recently, Tao et al. presented a new simple and efficient multivariate pubic key encryption scheme based on matrix multiplication, which is called Simple Matrix Scheme or ABC. Using linearization equation attack, we propose a polynomial time algorithm, which directly recovers an equivalent private key from the public key of ABC. Furthermore, our attack can also be applied to the variants of ABC since these variants have the same algebraic structure as the original ABC scheme. Therefore, the ABC cryptosystem and its variants are insecure.

Category / Keywords: public-key cryptography / public key cryptography, multivariate pubic key, linearization attack, cryptanalysis

Date: received 16 Nov 2016, last revised 16 Nov 2016

Contact author: chunsheng_gu at 163 com

Available format(s): PDF | BibTeX Citation

Version: 20161117:022459 (All versions of this report)

Short URL: ia.cr/2016/1075

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]