On Enumeration of Polynomial Equivalence Classes and Their Application to MPKC

Dongdai Lin; Jean-Charles Faugere; Ludovic Perret; Tianze Wang

Paper 2011/055

On Enumeration of Polynomial Equivalence Classes and Their Application to MPKC

Dongdai Lin, Jean-Charles Faugere, Ludovic Perret, and Tianze Wang

Abstract

The Isomorphism of Polynomials (IP) is one of the most fundamental problems in multivariate public key cryptography (MPKC). In this paper, we introduce a new framework to study the counting problem associated {to} IP. Namely, we present tools of finite geometry allowing to investigate the counting problem associated to IP. Precisely, we focus on enumerating or estimating the number of isomorphism equivalence classes of homogeneous quadratic polynomial systems. These problems are equivalent to finding the scale of the key space of a multivariate cryptosystem and the total number of different multivariate cryptographic schemes respectively, which might impact the security and the potential capability of MPKC. We also consider their applications in the analysis of a specific multivariate public key cryptosystem. Our results not only answer how many cryptographic schemes can be derived from monomials and how big the key space is for a fixed scheme, but also show that quite many HFE cryptosystems are equivalent to a Matsumoto-Imai scheme.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: multivariate public key cryptography polynomial isomorphism finite geometry equivalence classes superfluous keys
Contact author(s): d_d_lin @ yahoo com cn
History: 2011-01-30: received
Short URL: https://ia.cr/2011/055
License: CC BY

BibTeX

@misc{cryptoeprint:2011/055,
      author = {Dongdai Lin and Jean-Charles Faugere and Ludovic Perret and Tianze Wang},
      title = {On Enumeration of Polynomial Equivalence Classes and Their Application to {MPKC}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/055},
      year = {2011},
      url = {https://eprint.iacr.org/2011/055}
}