Paper 2020/053

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

Yasuhiko Ikematsu and Shuhei Nakamura

Abstract

A Gr¥"{o}bner basis algorithm computes a good basis for an ideal of a polynomial ring and appears in various situations of cryptography. In particular, it has been used in the security analysis of multivariate public key cryptography (MPKC), and has been studied for a long time; however, it is far from a complete understanding. We consider the algebraic attack using a Gr¥"{o}bner basis algorithm for a new multivariate encryption scheme proposed by Jiahui Chen et al. at Theoretical Computer Science 2020. Their idea to construct a new scheme was to use the minus and plus modifiers to prevent known attacks, such as linearization attack. Moreover, they discussed to have a resistance to the algebraic attack using a Gr¥"{o}bner basis algorithm. However, in our experiments, the algebraic attack breaks their claimed 80- and 128-bit security parameters in reasonable times. It is necessary to understand whether their scheme can avoid such an attack by introducing a slight modification. In this paper, we theoretically describe why the algebraic attack breaks their scheme and give a precise complexity of the algebraic attack. As a result, we demonstrate that the algebraic attack can break the claimed 80- and 128-bit security parameters in the complexities of approximately 25 and 32 bits, respectively. Moreover, based on our complexity estimation of the algebraic attack, we conclude that Chen et al.'s scheme is not practical.