Lite-Rainbow: Lightweight Signature Schemes Based on Multivariate Quadratic Equations and Their Secure Implementations

摘要

Rainbow signature scheme based on multivariate quadratic equations is one of alternatives to guarantee secure communications in the post-quantum world. Its speed is about dozens of times faster than classical public-key signatures, RSA and ECDSA, while its key size is much heavier than those of the classical ones. We propose lightweight variants of Rainbow, Lite-Rainbow-0 and Lite-Rainbow-1, for constrained devices. By replacing some parts of a public key or a secret key with small random seeds via a pseudo-random number generator, we reduce a public key in Lite-Rainbow-1 and a secret key in Lite-Rainbow-0 by factors 71 % and 99.8%, respectively, compared to Rainbow. Although our schemes require additional costs for key recovery processes, they are still highly competitive in term of performance. We also prove unforgeability of our scheme with special parameter sets in the random oracle model under the hardness assumption of the multivariate quadratic polynomial solving problem. Finally, we propose countermeasures of Rainbow-like schemes against side channel attacks such as power analysis for their secure implementations.