Design And Analysis Of Multivariate Public Key Cryptosystem

The speeds of traditional public key cryptographic algorithms are relatively low, which hamper their further applications. With the development of quantum computation, the designs of new and fast public key cryptographic algorithms are motivated in the cryptographic community. The multivariate public key cryptosystem is a new and fast public key cryptosystem, and its security assumption is based on the difficulty of solving a set of multivariate polynomial equations over a finite field. Moreover, compared with traditional public key cryptosystems based on large integer factorization and discrete logarithm problems, the multivariate public key cryptosystem is not only more computationally efficient, but also resistant to the quantum algorithm. This paper investigates the design and analysis of multivariate public key cryptosystem, and the author obtains the following main results:1. We present an algebraic method to attack the candidate dragon signature algorithm. The basic idea of the attack is to utilize the underlying algebraic structure of the candidate dragon signature algorithm over the extension field to derive a way to enable the variable Y be viewed as a fixed value. When the parameters of the candidate dragon signature algorithm are small enough, the attack can recover the private keys.2. We propose an algebraic method to attack the projected C*- scheme. The basic idea of the attack is to apply the affine parts of the private keys and the weakness caused by the structures of the private keys to find a large number of linear equations. Meanwhile, the weak keys of the scheme are found and the private keys can be recovered once the weak keys are used. We also present a new modification of C*-scheme, which is not only as efficient as original projected C*- scheme, but also resistant to the differential attack and the attack proposed in this paper.3. We propose an improved RMPKC scheme. The basic idea of the improvement is that the degree of the function of the first rational mapping is changed to three while the degree of the second remains to two. It is proved that the requirement for conducting the 2R decomposition attack is not fulfilled in the improved scheme. 4. We propose a multivariate public key cryptographic scheme over finite fields with odd characteristic. The idea of embedding and layering is manifested in its construction. We analyze the security of the scheme in detail.5. The problem of equivalent keys in the multivariate public key cryptosystem is investigated. We define the Plus sustaining transformation and present its expression. The number of equivalent keys in some multivariate public key cryptographic schemes is computed respectively with the Plus sustaining transformation and other sustaining transformations.