Cryptography Reference
In-Depth Information
However, Pollard and Schnorr proposed an algorithm to solve the equation (1)
eciently without factorizing
N
. OSS signature scheme was then extended in
two ways.
In 1994, Shamir [21] proposed a multivariate variant of OSS signature scheme,
called Birational Permutation scheme. However, Coppersmith, Stern and Vau-
denary [5] presented an ecient attack by observing a linear combination of
components of the public key.
In 1997, Sato and Araki [20] extended from OSS signature scheme using
quaternion algebra. Here, they replaced
Z
/N
Z
in OSS signature scheme using
quaternion algebra over
. However, Coppersmith then found two ecient
attacks using a special property of quaternion algebra.
In 2008, Hashimoto and Sakurai [10] proposed a new scheme (HS scheme),
including the properties of both Birational Permutation scheme and Sato-Araki
scheme. In 2010, Uchiyama and Ogura [22] showed that this scheme can be
reduced to Rainbow, which is a signature scheme in the multivariate public key
cryptosystem (MPKC), and discussed the possibility of forgery in the case of HS
scheme with a small size.
Non-commutative rings often appear in cryptography, for example, in Sato-
Araki scheme and HS scheme. Quaternion algebras and group rings are known
as typical examples of non-commutative rings. They have a complex algebraic
structure, which provides for cryptographic applications. There are two areas of
cryptographic interest in the study of both non-commutative rings and OSS sig-
nature scheme. One is the relationship between security, eciency and a choice
of a non-commutative ring in HS scheme. Another is a reconstruction of the HS
scheme as a part of MPKC which is a candidate for a post-quantum cryptosys-
tem. This paper is a report on the latter.
Works related to non-commutative rings, other than Sato-Araki scheme and
HS scheme include the non-commutative version of Polly Cracker [19] and the
cryptography using the Braid group ([1],[11]).
Birational Permutation scheme can be rewritten as a scheme in MPKC by
naturally changing a base ring
Z
/N
Z
for a Galois field. We apply this method to
HS scheme in order to construct a new MPKC scheme. In addition, we consider
the security against known MPKC attacks.
By carefully observing how Uchiyama and Ogura reduced HS scheme to Rain-
bow, it becomes clear that our object, as a cryptosystem, is included in the class
of Rainbow in which all components in the parameter are equal. In this paper,
we refer to such a Rainbow as a uniformly-layered Rainbow. When Rainbow has
3 layers, in order to be secure, parameters whose components are nearly equal
are selected [16]. Therefore, it is worth observing the uniformly-layered Rain-
bow. The setting of uniformly-layered Rainbow has not yet been studied, and its
security is discussed for the first time in this paper. In addition, in the appendix,
we try to extend HS scheme, which loosens the condition of non-commutative
rings.
In our propose scheme, a finite field with a small order is used as a base ring.
IntheoriginalHSscheme,thebaseringis
Z
/N
Z
Z
/N
Z
. Therefore, the arithmetic
