A new perturbed matsumoto-imai signature scheme

ABSTRACT

Two new modification methods, triangular perturbation and dual perturbation, are proposed for multivariate signature schemes to enhance the security with almost no loss of efficiency. A new multivariate signature scheme is then constructed by applying the two new methods together to the well-known Matsumoto-Imai cryptosystem. This new signature scheme has a specially designed structure making it have several competitive advantages: 1) the public map remains surjective (this property is important for a signature scheme), 2) it is almost as efficient as the original scheme and 3) it can resist all current known structure-based attacks to MPKC and behave like a random system against direct attacks. A new efficient and effective modification method is thus provided for multivariate signature schemes.

References

1. J. Ding. A new variant of the Mausomoto-Imai cryptosystem through perturbation. In F. B. et al, editor, PKC 2004, volume 2947 of LNCS, pages 305--318. Springer, 2004.
2. J. Ding, J. E. Gower, and D. S. Schmidt. Multivariate public key cryptosystems, volume 25 of Advances in Information Security. Springer, 2006.
3. J. Ding and D. Schmidt. Cryptanalysis of HFEv and the internal perturbation of HFE. In S. Vaudenay, editor, PKC 2005, volume 3386 of LNCS, pages 288--301. Springer, 2005.
4. P.-A. Fouque, L. Granboulan, and J. Stern. Differential cryptanalysis for multivariate schemes. In R. Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 341--353. Springer, 2005.
5. M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman, 1979.
6. M. Gotaishi, K. Tadaki, R. Fujita, and S. Tsujii. Dually-Perturbed Matsumoto-Imai Signature (DPMS) Scheme. IEICE Trans. Fundamentals, E93-A(6), June 2010.
7. A. Kipnis, J. Patarin, and L. Goubin. Unbalanced oil and vinegar signature schemes. In J. Stern, editor, EUROCRYPT'99, volume 1592 of LNCS, pages 206--222. Springer, 1999.
8. A. Kipnis and A. Shamir. Cryptanalysis of the HFE public key cryptosystem by relinearization. In M. Wiener, editor, CRYPTO'99, volume 1666 of LNCS, pages 19--30. Springer, 1999.
9. T. Matsumoto and H. Imai. Public quadratic polynomial-tuples for efficient signature verification and message encryption. In C. G. Guenther, editor, EUROCRYPT'00, volume 330 of LNCS, pages 419--453. Springer, 1988.
10. J. Patarin. Hidden field equations (HFE) and isomorphism of polynomials (IP): Two new families of asymmetric algorithms. In U. Maurer, editor, EUROCRYPT'96, volume 1070 of LNCS, pages 33--48. Springer, 1996.
11. J. Patarin, L. Goubin, and N. Courtois. C*- and HM: variations around two schemes of T. Matsumoto and H. Imai. In K. Ohta and D. Pei, editors, ASIACRYPT'98, volume 1514 of LNCS, pages 35--50. Springer, 1998.
12. E. Thomae. A generalization of the rainbow band separation attack and its applications to multivariate schemes.hrefhttp://eprint.iacr.org/2012/223.pdfhttp://eprint.iacr.org/2012/223.pdf, 2012.
13. E. Thomae and C. Wolf. Cryptanalysis of Enhanced TTS, STS and All Its Variants, or: Why Cross-Terms Are Important. In AFRICACRYPT, volume 7374 of LNCS, pages 188--202. Springer, 2012.
14. C. Wolf, A. Braeken, and B. Preneel. Efficient cryptanalysis of RSE(2)PKC and RSSE(2)PKC. In C. Blundo and S. Climato, editors, SCN 2004, volume 3352 of LNCS, pages 294--309. Springer, 2005.
15. C. Wolf, A. Braeken, and B. Preneel. On the security of stepwise triangular systems. Des Codes Crypt, 40:285--302, 2006.
16. C. Wolf and B. Preneel. Taxonomy of public key schemes based on the problem of multivariate quadratic equations. Cryptology ePrint Archive, Report 2005/077, http://eprint.iacr.org/2005/077/http://eprint.iacr.org/2005/077/, 2005.
17. T. Yasuda, T. Takagi, and K. Sakurai. Multivariate signature scheme using quadratic forms. In P. Gaborit, editor, PQCrypto 2013, volume 7932 of LNCS, pages 243--258. Springer, 2013.

Index Terms

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques

      • Public key encryption