Cryptology ePrint Archive: Report 2009/245

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

Naoki Ogura and Shigenori Uchiyama

Abstract: 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.

Category / Keywords: public-key cryptography / public-key cryptography, non-commutative ring, birational permutation, Rainbow, Groebner basis

Date: received 29 May 2009, last revised 30 May 2009

Contact author: ogura-naoki at ed tmu ac jp

Available format(s): PDF | BibTeX Citation

Version: 20090531:021540 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]