A Way To Build A UOV Variant With Shorter Private Key And Faster Signature Generation

In the current public key cryptosystems, RSA, ECC, El Gamal are the most popular algorithms. These schemes are still secure and widely in use these days. However, according to the Shor’s algorithm proposed by Peter Shor at 1994, a quantum computer could factorize a large integer in polynomial time which makes all these algorithms based on traditional number theory under severe security threats.Since the Shor’s algorithm was proposed, quantum computers have undergone rapid development. Some micro models have already been made and they could factorize small integers. In the near future, a powerful quantum computer’s appearance will be realistic. Thereby, it’s urgent to find an alternative for traditional public key cryptosystems. Some main branches of public key cryptogtaphy in post-quantom era includes:(1)Lattice-based Cryptography;(2) Hash-based Cryptography;(3) Code-based Cryptography;(4)The last one is the focus of this paper: Multivariate Public Key cryptography(MPKC for short).Compare to the traditional public key cryptosystems, MPKCs’ security depends on solving a random quadratic multivariate equations based on a finite field is NP-hard. Current research indicates that quantum computers can’t effectively solve this kind of problems.Multivariate public key cryptosystems are usually highly efficient in computing. Public/private key generation, encryption and decryption, signature verification and so on can be accomplished in a very short time. This an obvious advantage it intends to be im[lemented on the devices with limited computing capacity such as smart card, RFID. On the other hand, large size of the public,/private key, lack of strict security proof are the major drawbacks of this kind of cryptosystems. There is still a long way to go before put into applications for Multivariate public key cryptosystems.This paper will propose a method to build a variant of a famous MPKC signature scheme: UOV which usually has overlarge key size. This paper’s UOV has shorter privite key size and faster signature generation speed.