Cryptography Reference
In-Depth Information
A Security Analysis of Uniformly-Layered
Rainbow
Revisiting Sato-Araki's Non-commutative Approach to
Ong-Schnorr-Shamir Signature towards PostQuantum Paradigm
Takanori Yasuda
1
and Kouichi Sakurai
1
,
2
1
Institute of Systems, Information Technologies and Nanotechnologies
2
Department of Informatics, Kyushu University
Abstract.
In 1984, Ong, Schnorr and Shamir proposed an ecient sig-
nature scheme (OSS signature scheme) using a bivariate quadratic equa-
tion. Its security was believed to be based on the diculty of integer
factorization. However, an ecient attack without integer factorization
was subsequently found. In 2008, Hashimoto and Sakurai proposed an ex-
tended 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 mul-
tivariate 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 cor-
responding 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.
Keywords:
Multivariate Public Key Cryptosystem, Post-quantum cryp-
tography, Digital signature, Rainbow, Non-commutative ring.
1
Introduction
In 1984, Ong, Schnorr and Shamir [14] proposed an ecient signature scheme
(OSS signature scheme) using the following bivariate quadratic equation,
x
2
+
hy
2
≡
m
mod
N
(1)
where
N
is a composite number that cannot easily be factorized. The security of
this scheme was supposed to be based on the diculty of integer factorization.
