On Enumeration of Polynomial Equivalence Classes and Their Application to MPKC

Date Added: Jan 2011
Format: PDF

The Isomorphism of Polynomials (IP) is one of the most fundamental problems in Multivariate Public Key Cryptography (MPKC). In this paper, the authors introduce a new framework to study the counting problem associated to IP. Namely, they present tools of finite geometry allowing to investigate the counting problem associated to IP. Precisely, they 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.