Abstract

In this paper, we investigate the question of keys for MFE (Medium Field Equation) multivariate public key system and show that the MFE scheme also allows many superfluous equivalent keys. By applying permutation sustaining transformations, we partition the private key space into equivalence classes. A relationship describing the number of private keys in each equivalence class is established. And the formula shows that the number of private keys corresponding to any given public key is exponential. Hence the scheme has a smaller private and public key space than initially expected. The results reveal the inner relation between the keys and show their applications in cryptanalysis.

Paper Details