Paper 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.