Paper 2009/245

Cryptanalysis of the Birational Permutation Signature Scheme over a Non-commutative Ring

Naoki Ogura and Shigenori Uchiyama


In 2008, Hashimoto and Sakurai proposed a new efficient signature scheme, which is a non-commutative ring version of Shamir’s birational permutation signature scheme. Shamir’s scheme is a generalization of the OSS (Ong-Schnorr-Shamir) signature scheme and was broken by Coppersmith et al. using its linearity and commutativity. The HS (Hashimoto-Sakurai) scheme is expected to be secure against the attack of Coppersmith et al. since the scheme is based on the noncommutative structure. In this paper, we propose an attack against the HS scheme. Our proposed attack is practical under the condition that its step size and the number of steps are small. More precisely, we firstly show that the HS scheme is essentially a commutative scheme, that is, the HS scheme can be reduced to some commutative birational permutation signature scheme. Then we apply Patarin-like attack against the commutative birational permutation signature scheme. We discuss efficiency of our attack by using some experimental results. Furthermore the commutative scheme obtained from the HS scheme is the Rainbow-type signature scheme. We also discuss the security of the Rainbow-type signature scheme, and propose an efficient attack against some class of the Rainbow-type signature scheme.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
public-key cryptographynon-commutative ringbirational permutationRainbowGroebner basis
Contact author(s)
ogura-naoki @ ed tmu ac jp
2009-05-31: revised
2009-05-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Naoki Ogura and Shigenori Uchiyama},
      title = {Cryptanalysis of the Birational Permutation Signature Scheme over a Non-commutative Ring},
      howpublished = {Cryptology ePrint Archive, Paper 2009/245},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.