Security Analysis on an ElGamal-Like Multivariate Encryption Scheme Based on Isomorphism of Polynomials

Isomorphism of polynomials with two secrets (IP2S) problem was proposed by Patarin et al. at Eurocrypt 1996 and the problem is to find two secret linear maps filling in the gap between two polynomial maps over a finite field. At PQC 2020, Santoso proposed a problem originated from IP2S, which is called block isomorphism of polynomials with circulant matrices (BIPC) problem. The BIPC problem is obtained by linearizing IP2S and restricting secret linear maps to linear maps represented by circulant matrices. Using the commutativity of products of circulant matrices, Santoso also proposed an ElGamal-like encryption scheme based on the BIPC problem. In this paper, we give a new security analysis on the ElGamal-like encryption scheme. In particular, we introduce a new attack (called linear stack attack) which finds an equivalent key of the ElGamal-like encryption scheme by using the linearity of the BIPC problem. We see that the attack is a polynomial-time algorithm and can break some 128-bit proposed parameters of the ElGamal-like encryption scheme within 10 h on a standard PC.