Solving the problem of Blockwise Isomorphism of Polynomials with Circulant matrices

摘要

The problem of Isomorphism of Polynomials (IP problem)is known to be important to study the security of multivariate public keycryptosystems, one of the major candidates of post-quantum cryptography,against key recovery attacks. In these years, several schemes based on theIP problem itself or its generalization have been proposed. At PQCrypto2020, Santoso introduced a generalization of the problem of Isomorphism ofPolynomials, called the problem of Blockwise Isomorphism of Polynomials(BIP problem), and proposed a new Diffie-Hellman type encryption schemebased on this problem with Circulant matrices (BIPC problem). Quiterecently, Ikematsu et al. proposed an attack called the linear stack attackto recover an equivalent key of Santoso’s encryption scheme. While thisattack reduced the security of the scheme, it does not contribute to solvingthe BIPC problem itself. In the present paper, we describe how to solvethe BIPC problem directly by simplifying the BIPC problem due to theconjugation property of circulant matrices. In fact, we experimentallysolved the BIPC problem with the parameter, which has 256 bit security bySantoso’s security analysis and has 72.7 bit security against the linear stackattack, by about 10 minutes.