Cryptology ePrint Archive: Report 2020/053

Security Analysis Against "A New Encryption Scheme for Multivariate Quadratic Systems"

Yasuhiko Ikematsu and Shuhei Nakamura

Abstract: Multivariate encryption schemes are public key encryption schemes using multivariate polynomials over finite fields. In 2020, Jiahui Chen et al. proposed a new multivariate encryption scheme. In order to construct the public key consisting of quadratic polynomials, they used the minus and plus modifiers to prevent known attacks, such as linear equations attack, minRank attack and algebraic attack. However, in this paper we show that even if such modifiers are used, an attack using linear algebra is valid for their scheme. In fact, our attack can break the claimed 80 and 128-bit parameters in the complexity of around 27 and 31 bits, respectively.

Category / Keywords: public-key cryptography / Multivariate Public-Key Cryptography

Date: received 17 Jan 2020, last revised 19 Jan 2020

Contact author: ikematsu at imi kyushu-u ac jp

Available format(s): PDF | BibTeX Citation

Version: 20200120:192758 (All versions of this report)

Short URL: ia.cr/2020/053


[ Cryptology ePrint archive ]