The Design And Analysis Of Bipolar And Mixed Multivariate Public Key Cryptosystems

Multivariate public key cryptography that potentially resist quantum computer attacks is an important post quantum cryptotechnique. The structure of multivariate cryptosystem is very special, because its public key consists of a set of nonlinear multivariate polynomials over a finite field. Most importantly, multivariate public key cryptosystems are in general much more computationally efficient than conventional public key schemes based on number theory. Con-sequently, they are not only used in secure communication systems such as electronic commerce, education system, military system and other secure systems, but also applied to devices or en-vironments with limited resources such as USB token, low-cost smart card, RFID tag, vehicle system, mobile phone, palm device and other embedded devices. In a word, multivariate public key cryptotechnique has a very high research value, and deserves our attentions.However, for the moment there exist some obstacles in the way of multivariate public key cryptography. For example, lack of secure multivariate schemes (especially for mixed-type ones), few types of basic trapdoor, oversize public key, and being difficult to prove their securi-ties by the formal method. To solve these problems, we devote the design of multivariate public key cryptosystem, and focus on both the bipolar system and the mixed system. We then propose a bipolar-type multivariate public key cryptosystem named TOT and a mixed-type multivari-ate public key signature scheme called RGB. At last, we employ the identity-based semantics to solve the problem of the oversize public key, and present a new identity-based multivariate signature scheme with provable security called IBUOV. In this dissertation, we introduce these three schemes, analyse detailedly their securities, evaluate comprehensively their performances, and compare them with other public key cryptosystems (do experiments for their implementa-tions). The specific contents are as follows.In Chapter 4, we design a novel one-way trapdoor function, and then employ it to propose a new multivariate public key cryptosystem called TOT, which can be used for encryption, signa-ture and authentication. Through analysis, we find that TOT can resist current known algebraic attacks under proper parameters, including exhaustive search attack, affine multiple attack, lin-earization equation attack, Kipnis-Shamir attack, distillation attack, differential attack, Grobner basis attack and XL attack. According to these attacks, we give the attack complexity for TOT, and provide some security parameters (at least in 280). In order to show the performance of TOT, we compare TOT with other public key cryptosystems including multivariate schemes and non-multivariate schemes. The comparison shows that TOT can gain easily a higher secu-rity level than HFE, HFEv and Quartz. Meanwhile, increasing appropriately the security level of TOT does no harm to the computing speed of its secret map. On the 80-bit security level, the experiment shows that the decryption time (or the signing time) of Magma implementation of TOT is 0.202 s on an ordinary PC with 2.50 GHz; the signing time of C/C++ implementation of TOT is 8.60 ms. Obviously, on the same security level, the decryption speed of TOT is faster than that of HFE and PMI+; the signing speed of TOT is faster than that of HFEv, Quartz and RSA-1024. Moreover, the computing speed of the secret map of TOT is almost the same as both C* and Sflashu2 from the structural point of view (even though C* was broken, its high speed has been affirmed).In Chapter 5, we first define a particular polynomial called Three-color Polynomial and its corresponding Three-color Map. This polynomial has three-class variables, and the form of the associated symmetric matrix of its quadratic part is similar to the three-color model in colorimetry, so we call it three-color polynomial. Based on the three-color map, we then present a mixed multivariate signature scheme named RGB (it means Red-Green-Blue). Because each polynomial of the central map of RGB has a great deal of quadratic cross-terms among all the variables, the variable values of the central map can be more fully mixed with the message values. This is a good job because the number of cross-terms can determine the security level of the system to a certain degree. Generally speaking, the more the cross-terms are, the more secure the system is; the more the variables are, the more secure the system is. Through detailed analysis, we find that RGB can resist current known algebraic attacks under proper parameters, such as exhaustive search attack, separation attack, MinRank attack and direct attack. While other algebraic attacks, such as Thomae-Wolf attack, high rank attack, linearization equation attack, differential attack, are inapplicable for RGB. Besides, our experiment shows that, on the 80-bit security level, the signing time of Magma implementation of RGB is 0.046 s on an ordinary PC with 2.50 GHz; the signing time of C implementation of RGB is 3.10 ms on an 800 MHz machine. The comparison shows that, on the same security level, the signing speed of RGB is faster than that of Sflashu2, Quartz, UOV, Rainbow and RSA-1024, while slower slightly than that of ECDSA-163 and NTRUSign-251. All in all, this new scheme makes a very good performance in terms of security and efficiency.In Chapter 6, we make use of the identity-based semantics to solve the problem of the oversize public key, then propose an identity-based unbalanced Oil-Vinegar signature scheme called IBUOV according to the constructive idea of certificate-based identity-based signature scheme. IBUOV is a variant of the UOV signature scheme, its security strictly relies on UOV We provide the provable security to explain that. As is known to us, it is very difficult to prove the security of multivariate cryptosystem by the formal technique. Therefore, our method does not possess the characteristic of the general security model, but it can be deemed to be the preliminary study of multivariate provable security, and is worth referencing. Comparing with UOV, the public key size of IBUOV is very small. On the same 80-bit security level, the public key size of UOV is 99.94 KB, while that of IBUOV is only 0.02 KB. It is thus clear that the identity-based semantics can solve the problem of the oversize public key of multivariate public key cryptosystem to some extent.