International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Yasufumi Hashimoto
Kouichi Sakurai
Download:
URL: http://eprint.iacr.org/2008/340
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-18017,
  title={On construction of signature schemes based on birational permutations over noncommutative rings},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / signature scheme},
  url={http://eprint.iacr.org/2008/340},
  note={ hasimoto@isit.or.jp 14095 received 4 Aug 2008},
  author={Yasufumi Hashimoto and Kouichi Sakurai},
  year=2008
}