Optimization And Analysis Of Rainbow And UOV Digital Signature Schemes

Public Key Cryptography is also known as Asymmetric Cryptography. A public key cryp-tography algorithm is usually based on a mathematically hard problem. Currently, all the popular public key algorithms are based on the three following hard problem-s:(1)Large integer fac-toring (RSA);(2)Discrete Logarithm problem(El-gamal);(3)Elliptic-Curve Discrete Logarithm problem(ECC);So far, these three kinds of algorithms can still meet the required security standards and they are widely used in our daily lives. However, according to Shor’s algorithm, with the devel-opment of quantum-computers, all these algorithms will be broken in a polynomial time. Ergo, it’s a very urgent matter to find a replacement of those traditional algorithms which can resist the attack of a powerful quantum computer in the near future.In the post-quantum cryptography, there are four main branches:1) Lattice-based cryptography;2) Hash-based Cryptography;3) Code-based Cryptography;4) Multivariate Public Key Cryptography(MPKC for short); Among them, MPKC is our focus and its security is based on a hard-problem that solving a random quadratic system over the chosen finite field is NP-hard. Quantum computers couldn’t efficiently solve this kind of problems.Usually, a MPKC scheme is highly efficient in computing and has an edge over applications on devices(e.g. Micro-Controllers, RFID) with limited computing capacity. On the other hand, MPKC schemes also have over-large public and private key sizes compared to traditional public key algorithms. Moreover, most of the MPKC schemes turn out to be insecure. They are lack of strict security proof.In this paper, we are going to propose some variants of two well-known MPKC schemes: UOV and Rainbow. They are more compact in public and private key size or more efficient in signature generating than the original schemes while they can meet required security level at the same time. These schemes are listed as follows:First of all, by adding corresponding quadratic terms, variables variation can be added to a Rainbow-like scheme which has higher security level against a popular attack in MPKC area: MinRank attack which also breaks the original Rainbow at the first time. Under the same security level against MinRank attack, our scheme has smaller key size(both public key and private key).Secondly, this paper builds a new secure variant of Rainbow by adding quadratic terms of the last layer to the last two layers. The main goal of constructing this variant of Rainbow is to resist Rainbow Band Separation(RBS) attack. Furthermore, by taking all the known attacks against Rainbow into consideration, we are able to come up with the corresponding set of pa-rameters which meets the required security level. This new variant has obvious advantages over storage compared to a regular Rainbow.Finally, inspired by the previous works of reducing the public key size for Rainbow, UOV and reducing the private key size, enhancing signing efficiency for Rainbow. This paper pro-poses two approaches to build UOV variants with shorter private key size and higher signing efficiency.