A variant of rainbow with shorter secret key and faster signature generation

Multivariate public key cryptosystems are being focused on as candidates for post-quantum cryptography. Rainbow is one of the most efficient signature schemes in multivariate public key cryptosystems. The main drawback of Rainbow is that their key size is much larger than that of RSA and ECC. In this paper, we propose an efficient variant of Rainbow that has a shorter secret key (and thus generates signatures faster) than the corresponding original Rainbow. In our scheme, we divide each layer of Rainbow into smaller blocks by using diagonal matrix representations. The size of the smaller blocks can be flexibly selected, and this enables us to carefully choose secure parameters so that our proposed scheme is secure against known attacks such as rank attacks, direct attacks, and UOV attack. We estimate that the secret key size of our proposed scheme with 100-bit security is smaller by about 40% than that of the original Rainbow. In addition, an implementation of our scheme in the C language is seen to generate signature faster by 40%.