skip to main content
research-article

A multivariate quadratic challenge toward post-quantum generation cryptography

Authors Info & Claims
Published:24 November 2015Publication History
Skip Abstract Section

Abstract

Multivariate polynomials over finite fields have found applications in Public Key Cryptography (PKC) where the hardness to find solutions provides the "one-way function" indispensable to such cryptosystems. Several schemes for both encryption and signature have been proposed, many of which are using quadratic (degree 2) polynomials. Finding a solution to such systems in general is called MQ problem, which easiest "generic" instances are NP-hard. An important feature of this Multivariate Pubic Key Cryptography (MPKC) is the resistance to quantum computers: no faster quantum algorithm than classical ones to solve MQ problem is known. Besides being thereby a candidate for Post-Quantum Cryptography, signatures are much shorter than to other candidates. We have established an open public "MQ Challenge" (https://www.mqchallenge.org) to stimulate progress in the design of efficient algorithms to solve MQ problem, and thus test limit parameters guaranteeing security of MPKC.

References

  1. Bernstein, D.-J., Buchmann, J. and Dahmen, E., "Post-quantum cryptography", Springer Science & Business Media, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Porras J., Baena J., and Ding J., "ZHFE, a New Multivariate Public Key Encryption Scheme", PQCrypto 2014, Springer LNCS vol. 8772, pp. 229--245, 2014.Google ScholarGoogle Scholar
  3. Ding J., Petzoldt A. and Wang L-C., "The Cubic Simple Matrix Encryption Scheme", PQCrypto 2014, Springer LNCS vol. 8772, pp. 76--87, 2014.Google ScholarGoogle Scholar
  4. Kipnis A., Patarin J. and Goubin, L., "Unbalanced Oil and Vinegar Schemes", Eurocrypt'99, Springer LNCS vol. 1592, pp. 206--222, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. Ding J. and Schmidt D., "Rainbow, a New Multivariable Polynomial Signature Scheme", ACNS 2005, Springer LNCS vol. 3531, pp. 164--175, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Petzoldt A., Bulygin S., Buchmann J., "Selecting Parameters for the Rainbow Signature Scheme", PQCrypto 2010, Springer LNCS vol. 6061, pp. 218--240, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. J.-C. Faugère, P. Gaudry, L. Huot, and G. Renault. "Sub-cubic change of ordering for Gröbner basis: A probabilistic approach". In Proceedings of ISSAC'14, pages 170--177. ACM, 2014. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. T. Yasuda, X. Dahan, Y.-J. Huang, T. Takagi, and K. Sakurai. "MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems". Cryptology ePrint Archive, Report 2015/275, 2015.Google ScholarGoogle Scholar

Index Terms

  1. A multivariate quadratic challenge toward post-quantum generation cryptography
      Index terms have been assigned to the content through auto-classification.

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in

      Full Access

      • Published in

        cover image ACM Communications in Computer Algebra
        ACM Communications in Computer Algebra  Volume 49, Issue 3
        September 2015
        45 pages
        ISSN:1932-2240
        DOI:10.1145/2850449
        Issue’s Table of Contents

        Copyright © 2015 Authors

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 24 November 2015

        Check for updates

        Qualifiers

        • research-article

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader