Paper 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.