Welcome to the resource topic for 2009/245
Title:
Cryptanalysis of the Birational Permutation Signature Scheme over a Non-commutative Ring
Authors: Naoki Ogura, 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.
ePrint: https://eprint.iacr.org/2009/245
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .