Optimization On Signing Efficiency And Key Size Of UOV-like Schemes And Their Implementations On Embedded Systems

In the past two decades, information technology industry has developed into a sunrise industry. It has successfully promoted the overall development of the social economy and the people's livelihood. Open network environment allows us to access to all aspects of the information, but also brings some security issues. Cryptography as a scientific research information focusing on security, has to take the responsibility to protect the information security. Cryptography is now divided into the traditional public key cryptography based on theory problems and post quantum cryptography. Because of quantum computer, Shor algorithm can effectively attack the traditional public key algorithm, like RSA algorithm based on large integer factorization, in polynomial time. The traditional public key cryptography algorithm cannot guarantee security. In order to resist the attack of the quantum computer, scholars began to study the post quantum cryptography, including lattice-based cryptography, multivariate public key cryptography(referred to MPKC) and hash-based cryptography. The security of MPKC is based on a NP-complete problem--MQ problem,solving a random quadratic system over a finite filed, and the quantum computer cannot solve the MQ problem with any advantage. The security of UOV signature algorithm in MPKC is well-known, but the key size is too large and limit its application.In this paper, the key size of UOV-like scheme is shorter and the signature efficiency has been improved. We proposed two kinds of UOV-like scheme, and introduced the structure,key size, signature efficiency and security analysis of the two algorithms in detail. Also, we have implemented UOV-like signature algorithm in the embedded system Tiny210, built the development board platform, transplanted the embedded Linux system and tested the proposed algorithms in the system by cross compilation. Experiments show that under the security level 2128, the private key size of UOV-like scheme is reduced by a factor up to more than 10 for ordinary UOV scheme and the signature generation time is only half of UOV. It is proved that UOV-like schemes have optimized the private key storage and improved the efficiency of performance in a very large scale.