Multivariate public key cryptosystems (MPKC) are public key cryptosystems, whose public key are a set of multivariate polynomials over a finite field (or ring). MPKC can be used for encryption, authentication and signatures. The invention develops three new methods that could be applied to a multivariate public key cryptosystem to produce new multivariate public key cryptosystems that are better in terms of security and efficiency. These three methods are called the internal perturbation plus (IPP), the enhanced internal perturbation (EIP) and the multi-layer Oil-Vinegar construction (MOVC). These three methods can be combined in any 2 or all 3 to be applied to a multivariate public key cryptosystem to produce new multivariate public key cryptosystems as well.