Analysis of Second Order Matrices Construction in MFE Public Key Cryptosystem

10.6633/IJNS.201601.18(1).17

Xu-Yun Nie；Chuan-Yong Hou；Zhao-Hu Xu；Gang Lu

Linearization equation ； MFE ； multivariate public key cryptosystem ； second order matrix

International Journal of Network Security

18卷1期（2016 / 01 / 01）

158 - 164

英文

Medium Field Equations (MFE), which is a type of multivariate public key encryptions scheme proposed by Wang et al., was broken by Ding et al. using high order linearization equation (HOLE) attack. Recently, many people attempt to modify the second order matrices structure in the central map of MFE to resist HOLE attack. In this paper, we gave deeply analysis of all possible constructions by products of the second order matrices and their variants with transpose and adjoint in the central map of MFE. We proved that any modification with transpose and adjoint would satisfy the First Order Linearization Equations or the Second Order Linearization Equations. As an example, we gave a practical cryptanalysis of an improved MFE scheme.