Cryptology ePrint Archive: Report 2021/169

Security Analysis on an El-Gamal-like Multivariate Encryption Scheme Based on Isomorphism of Polynomials

Yasuhiko Ikematsu and Shuhei Nakamura and Bagus Santoso and Takanori Yasuda

Abstract: 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 El-Gamal-like encryption scheme based on the BIPC problem. In this paper, we give a new security analysis on the El-Gamal-like encryption scheme. In particular, we introduce a new attack (called linear stack attack) which finds an equivalent key of the El-Gamal-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 El-Gamal-like encryption scheme within 10 hours on a standard PC.

Category / Keywords: public-key cryptography / Public Key Cryptography and Post Quantum Cryptography (PQC) and Multivariate Public Key Cryptography (MPKC) and Isomorphism of Polynomials

Date: received 16 Feb 2021

Contact author: ikematsu at imi kyushu-u ac jp

Available format(s): PDF | BibTeX Citation

Version: 20210217:125534 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]