An Improved Medium-Field Multivariate Public-Key Encryption Scheme

The MFE cryptosystem proposed by Wang et al. uses medium-size field extensions, which makes faster. However, it is insecure due to SOLEs attack by Ding et al.. In this paper, we compose the central map of MFE with a new map to obtain an improved MFE MQ-scheme, which can resist the SOLEs attack. Meanwhile, with well-chosen parameters it can also resist rank attack and XL & Grobner bases attack. As far as we know, the idea of composing the central map with a new map to resist SOLEs (HOLEs) attack is put forward for the first time. It is possible to resist SOLEs (HOLEs) attack by composing the central map with a new map for all the broken mixed-field MQ-schemes.