A Security Analysis of Uniformly-Layered Rainbow

In 1984, Ong, Schnorr and Shamir proposed an efficient signature scheme (OSS signature scheme) using a bivariate quadratic equation. Its security was believed to be based on the difficulty of integer factorization. However, an efficient attack without integer factorization was subsequently found. In 2008, Hashimoto and Sakurai proposed an extended scheme (HS scheme), based on OSS signature scheme that used multivariate and non-commutative ring. HS scheme uses a composite number as a modulus in the same manner as OSS signature scheme.

In this paper, we redefine HS scheme in such a way that it deals with not only integers modulo a composite number, but also elements of a finite field. In the case of a finite field, it becomes a scheme in the multivariate public key cryptosystem. In fact, its public key is constructed by a version of Rainbow in which all the components in the parameter are equal. (We call such a Rainbow a uniformly-layered Rainbow.) In particular, our scheme is a candidate for post-quantum cryptography. If a non-commutative ring used in the proposed scheme is chosen by the group ring associated to dihedral group, the speed of the signature generation can be accelerated by about 50% in comparison with the corresponding Rainbow. We analyze the security of the extended HS scheme against some attacks and conclude that if its base field is

GF

(256), then the dimension of a non-commutative ring must be more than 10 in order to be secure.