Cryptanalysis Of Severalmultivariate Public Key Cryptosystems

In recent years, Multivariate Public Key Cryptosystem （MPKC） has developedrapidly in the field of cryptography. MPKC can be regarded as one of the promisingalternatives to public key cryptosystem because it may resist quantum attack. Now,there are several MPKCs such as MI cryptosystem, Oil-Vinegar signature schemes,Medium Field Equation （MFE） cryptosystem, Extended Multivariate Public KeyCryptosystem （EMC） etc. Althouth the MFE was broken in2007, there are manyimprovements of MFE, whose designer claimed that they can resist all the existingattacks on MPKCs. As an enhanced scheme, the designer of the EMC claimed thatEMC can improve the MPKCs’security.In this thesis, we analyze the security of two improvements of MFE and HTTPencryptosystem as well as HTTM signature scheme which based on EMC scheme indetail. And we present the successful attacks on these schemes.MFE can’t resist High Order Linearization Equation （HOLE） attack because thereare many second order linearization equations satisfied by the central map of MFE. Inorder to resist HOLEs attack, two improvements were proposed by modifying thecentral map of the MFE. Through analysis of the central map in the two improvements,we found that, they can’t resist Second Order Linearization Equations （SOLEs） attack,even the First Order Linearization Equations （FOLEs） attack. In this thesis, we breakthese two improvements of MFE by FOLEs and HOLEs respectively. Thecomputational complexity is2³⁵ F_2¹⁶-operations and2⁵² F_2¹⁶-operations.EMC scheme is an enhanced scheme which can be used on all MPKCs to improvetheir security. EMC scheme use a nonlinear transformation based on hash function（HT）before the encryption of MPKCs. Through analysis, we found that, there exist a methodcan degrade the EMC scheme to the original MPKC. So we can use a similar attackmethod to break the EMC scheme as the method used to break the originalMPKC. Using this method，we successfully break the HTTP encryptosystem and theHTTM signature scheme. The computational complexity is2²⁸F_2^x-operations and 2⁴¹F_2^x-operations.At last，we verify all the attacks mentioned above by Magma in our computer andpresent many key algorithms which used to attack MPKCs.