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.
- Bernstein, D.-J., Buchmann, J. and Dahmen, E., "Post-quantum cryptography", Springer Science & Business Media, 2009. Google ScholarDigital Library
- 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 Scholar
- 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 Scholar
- Kipnis A., Patarin J. and Goubin, L., "Unbalanced Oil and Vinegar Schemes", Eurocrypt'99, Springer LNCS vol. 1592, pp. 206--222, 1999. Google ScholarDigital Library
- Ding J. and Schmidt D., "Rainbow, a New Multivariable Polynomial Signature Scheme", ACNS 2005, Springer LNCS vol. 3531, pp. 164--175, 2005. Google ScholarDigital Library
- Petzoldt A., Bulygin S., Buchmann J., "Selecting Parameters for the Rainbow Signature Scheme", PQCrypto 2010, Springer LNCS vol. 6061, pp. 218--240, 2010. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
Index Terms
A multivariate quadratic challenge toward post-quantum generation cryptography
Recommendations
Post-Quantum Lattice-Based Cryptography Implementations: A Survey
The advent of quantum computing threatens to break many classical cryptographic schemes, leading to innovations in public key cryptography that focus on post-quantum cryptography primitives and protocols resistant to quantum computing threats. Lattice-...
Post-challenge leakage in public-key encryption
When an adversary can measure the physical memory storing the decryption key, decryption functionality often comes in handy. Halevi and Lin (TCC'11) studied after-the-fact (or post-challenge) leakage in public-key encryption (PKE), in which an adversary ...
Comments