Study On Public Key Cryptographic Schemes Based On Multivariate Polynomials

Among the alternative PKCs that are weakened by quantum computers (via Shor's Algorithm), multivariate public key cryptography is a new kind of PKC and attracts people's great interesting. The system uses neither factoring (like RSA, Rivest-Shamir Adleman) nor the discrete logarithm (like ECC, elliptic curve cryptography). It relies on the problem that solving multivariate nonlinear equations over finite fields is NP-complete.In this dissertation, multivariate pubic key cryptosystems on finite fields are investigated. The main fruits are summarized as follows:1. The Medium-Field multivariate public key encryption scheme given by Wang et al was defeated by the second order linearization equation attack presented by Ding et al. An improved encryption scheme was proposed. The central map of the original scheme was redesigned and the related linear equations can not be calculated by the attacker, and then the new variant can avoid the second order linearization equation attack. Analysis shows that the enhanced variant can resist the second order linearization equation attack, Linearization attack, Rank attacks, XL algorithm, and Gr?bner-based method. It is a more security encryption scheme.2. A result that the equivalent private keys are determined by the sustainers is proved. Then the superfluous key problem for multivariate quadratic cryptosystems on medium fields is investigated. By applying sustainers, the private key space can be divided into equivalence classes, and we indicate that the superfluous equivalent keys are the nature existence of the multivariate cryptosystem. What's more, based on the isomorphism ideology, the central mapping on the extension field is transformed into the base field; a relationship between the number of secret keys in each equivalence class and the quantum of plaintext and ciphertext components is established. The formula estimates the lower limit of the equivalent keys and shows that the number of secret keys corresponding to any given public key is exponential. Hence the scheme has a smaller private and public key space than initially expected.3. By introducing"additional signature values"and another signature verification called"internal verification", we present a new multivariate signature model. The work is accomplished by combing a homomorphic hash function with some secret information hidden in the central mapping of the scheme. The analysis on the MFE scheme under the model shows that the model is more effective to resist the known attacks.4. Since most of the known multivariate public key signature schemes are under attacks, an improved signature model is proposed by analyzing the structure of the classical model. The model is redesigned,by adding another secret transformation so that the public key polynomials are not correspondence to the composition of the private keys, that is not the case in classical model, and the message value is hidden, then the amount of information obtained by attacker are reduced, and then scheme performance against attacks is enhanced. We take L-IC ? scheme as an example to illustrate the idea and theoretical analysis shows that L-IC ? scheme by the model can resist the attack proposed by Fouque et al.5. A sufficient and necessary condition on verifying whether a polynomial of arbitrary degree over finite fields is irreducible (or primitive) or not is deduced, then an efficient and deterministic algorithm is proposed to determine a polynomial over finite fields is irreducible (or primitive) or not.