Cryptology ePrint Archive: Report 2008/340

On construction of signature schemes based on birational permutations over noncommutative rings

Yasufumi Hashimoto and Kouichi Sakurai

Abstract: In the present paper, we give a noncommutative version of Shamir's birational permutation signature scheme proposed in Crypto'93 in terms of square matrices. The original idea to construct the multivariate quadratic signature is to hide a quadratic triangular system using two secret linear transformations. However, the weakness of the triangular system remains even after taking two transformations, and actually Coppersmith et al. broke it linear algebraically. In the non-commutative case, such linear algebraic weakness does not appear. We also give several examples of noncommutative rings to use in our scheme, the ring consisting of all square matrices, the quaternion ring and a subring of three-by-three matrix ring generated by the symmetric group of degree three. Note that the advantage of Shamir's original scheme is its efficiency. In our scheme, the efficiency is preserved enough.

Category / Keywords: public-key cryptography / signature scheme

Date: received 4 Aug 2008, withdrawn 4 Dec 2011

Contact author: hasimoto at isit or jp

Available format(s): (-- withdrawn --)

Version: 20111205:001737 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]