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

Yasuhiko Ikematsu; Shuhei Nakamura; Bagus Santoso; Takanori Yasuda

Paper 2021/169

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

Yasuhiko Ikematsu, Shuhei Nakamura, 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Contact author(s): ikematsu @ imi kyushu-u ac jp
History: 2021-02-17: received
Short URL: https://ia.cr/2021/169
License: CC BY

BibTeX

@misc{cryptoeprint:2021/169,
      author = {Yasuhiko Ikematsu and Shuhei Nakamura and Bagus Santoso and Takanori Yasuda},
      title = {Security Analysis on an El-Gamal-like Multivariate Encryption Scheme Based on Isomorphism of Polynomials},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/169},
      year = {2021},
      url = {https://eprint.iacr.org/2021/169}
}