Research On Design Theory Of Extended Multivariate Cryptosystems

Public key cryptography is an important tool for nowadays information society. Unfortunately, the security of public key schemes used in practice relies on two prob-lems:factoring(RSA) and discrete logarithms (ElGamal). Both problems are currently considered to be hard. Moreover, quantum computers have recently emerged as a threat to the RSA cryptosystem. Peter Shor discovered an algorithm that can be used to fac-torize an integer in polynomial time on a quantum computer. This means that once we have quantum computers that can deal with a large number of quantum bits, the RSA cryptosystem can no longer be considered secure. So we have a very strong mo-tivation to search for some efficient and secure alternative public key cryptosystems. There are mainly NTRU, McEliece, MPKCs and so on, which are currently believed to be resistant to quantum computing based attacks. In the last ten years, multivariate public key cryptosystems, or MPKCs for short, based on hard computational problems related to multivariate quadratic polynomials over a finite field, have increasingly been seen by some as a possible alternative to the public key cryptosystem RSA, which is widely in use today. Moreover, MPKC schemes are in general much more computa-tionally efficient than number theoretic-based schemes. By now, there are many new cryptographic schemes and constructions, and some of these schemes seem to be very suitable for small computing devices with limited computing capacity, such as smart cards, wireless sensor networks, and active RFID tags. Indeed, SFLASH, a multivariate signature scheme, was accepted as an European security standard for low-cost smart cards in 2003 by the New European Schemes for Signatures, Integrity and Encryption. Unfortunately, it was broken using the differential cryptanalysis by Dubois et al. in 2007. Furthermore, the current MPKCs can only be used for signing a message, it is difficult to construct a secure multivariate encryption algorithm, and the security of MPKCs has been questioned with some classical signature schemes defeated in recent years.This paper introduces the hash authentication techniques and combine with the traditional MQ-trapdoors to propose a novel hash-based multivariate public key cryp-tosystems. The resulting scheme, called EMC (Extended Multivariate Cryptosystem), can also be seen as a novel hash-based cryptosystems like Merkle tree signature. This scheme offers the double security protection for signing or encrypting. According to our analysis, we can construct the secure and efficient not only signature scheme but also encryption scheme by using the EMC scheme combined some modification methods summarized by Wolf. And thus we present two new schemes:EMC signature scheme (with the Minus method "-") and EMC encryption scheme (with the Plus method "+"). Meanwhile, we also propose a reduced scheme of the EMC signature scheme (a light-weight signature scheme). Precise complexity estimates for these schemes are provided, but their security proofs in the random oracle model are still an open problem. In addition, we also present an efficient encryption scheme whose security is based on the multivariate nonlinear polynomial equations of NP-hard problem over a finite field and combines with the theory of Error Correction Code.Cryptographic hash functions play a fundamental role in modern cryptography, particularly in data integrity, message authentication, and digital signature. Probably the most popular hash functions in use today are MD5 and SHA-1 which have been standardized by the National Institute of Standards and Technology (NIST) in the U.S.. However, some important cryptanalysis results have shown weaknesses that allow collisions to be computed for these hash functions much faster than by brute force. Hence there is a rather pressing need to design new hash functions as of today (cf. NIST's competition for a new hash standard).This paper proposes a novel hash algorithm whose security is based on the multi-variate nonlinear polynomial equations of NP-hard problem over a finite field and com-bines with HAIFA iterative framework. Over the current widely used hash algorithms, the new algorithm has the following advantages:its security is based on a recognized difficult mathematical problem; the hash length can be changed freely; its design can be automated such that users may construct specific hash function meeting the actual needs. Furthermore, we discuss the security, efficiency and performance of the new algo-rithm. Under some related difficult mathematical assumptions and theoretical analysis, the new algorithm is proven practical by the experiment results, and capable of achiev-ing security of an ideal hash function by choosing suitable parameters. In addition, it can also be used as a pseudo-random number generator for the good randomness of its output.Concretely, the following aspects are investigated deeply in this paper:1. A novel multivariate public key cryptosystem, called EMC (Extended Multi-variate Cryptosystem), is proposed by introducing the hash authentication techniques. According to our analysis, we can construct the secure and efficient not only signature scheme but also encryption scheme by using the EMC scheme combined some modifi-cation methods summarized by Wolf.2. A light-weight signature based on a reduced scheme of the EMC signature scheme is proposed, and experimental results show that it is more efficient than all of the current digital signature schemes.3. We also present an efficient encryption scheme whose security is based on the multivariate nonlinear polynomial equations of NP-hard problem over a finite field and combines with the Niederreiter cryptosystems.4. We propose a novel hash algorithm whose security is based on the multivariate nonlinear polynomial equations of NP-hard problem over a finite field and combines with HAIFA iterative framework. Under some related difficult mathematical assumptions and theoretical analysis, the new algorithm is proven practical by the experiment results, and capable of achieving security of an ideal hash function by choosing suitable parameters. In addition, it can also be used as a pseudo-random number generator. We believe that the new Hash algorithm has extensive potential applications.