nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Extension Field Cancellation: A New Central Trapdoor for Multivariate Quadratic Systems

verfasst von : Alan Szepieniec, Jintai Ding, Bart Preneel

Erschienen in: Post-Quantum Cryptography

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper introduces a new central trapdoor for multivariate quadratic (MQ) public-key cryptosystems that allows for encryption, in contrast to time-tested MQ primitives such as Unbalanced Oil and Vinegar or Hidden Field Equations which only allow for signatures. Our construction is a mixed-field scheme that exploits the commutativity of the extension field to dramatically reduce the complexity of the extension field polynomial implicitly present in the public key. However, this reduction can only be performed by the user who knows concise descriptions of two simple polynomials, which constitute the private key. After applying this transformation, the plaintext can be recovered by solving a linear system. We use the minus and projection modifiers to inoculate our scheme against known attacks. A straightforward C++ implementation confirms the efficient operation of the public key algorithms.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On the Differential Security of the HFEv- Signature Primitive

Nächstes Kapitel Security Analysis and Key Modification for ZHFE

NESSIE: New European Schemes for Signatures, Integrity, Encryption 05 November 2014 (2003). https://www.cosic.esat.kuleuven.be/nessie/

Bettale, L., Faugère, J., Perret, L.: Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic. Des. Codes Crypt. 69(1), 1–52 (2013). http://dx.doi.org/10.1007/s10623-012-9617-2 CrossRefMATH

Billet, O., Patarin, J., Seurin, Y.: Analysis of intermediate field systems. IACR Cryptology ePrint Archive 2009, p. 542 (2009). http://eprint.iacr.org/2009/542

Courtois, N.T.: The security of Hidden Field Equations (HFE). In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 266–281. Springer, Heidelberg (2001). http://dx.doi.org/10.1007/3-540-45353-9_20 CrossRef

Ding, J., Hodges, T.J.: Inverting HFE systems is quasi-polynomial for all fields. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 724–742. Springer, Heidelberg (2011). http://dx.doi.org/10.1007/978-3-642-22792-9_41 CrossRef

Ding, J., Kleinjung, T.: Degree of regularity for HFE. In: IACR Cryptology ePrint Archive 2011, p. 570 (2011). http://eprint.iacr.org/2011/570

Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164–175. Springer, Heidelberg (2005). http://dx.doi.org/10.1007/11496137_12 CrossRef

Ding, J., Yang, B.-Y.: Degree of regularity for HFEv and HFEv. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 52–66. Springer, Heidelberg (2013). http://dx.doi.org/10.1007/978-3-642-38616-9_4 CrossRef

Ding, J., Yang, B., Cheng, C., Chen, C.O., Dubois, V.: Breaking the symmetry: a way to resist the new differential attack. IACR Cryptology ePrint Archive 2007, p. 366 (2007). http://eprint.iacr.org/2007/366

10.

Dubois, V., Fouque, P.-A., Shamir, A., Stern, J.: Practical cryptanalysis of SFLASH. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 1–12. Springer, Heidelberg (2007). http://dx.doi.org/10.1007/978-3-540-74143-5_1 CrossRef

11.

Dubois, V., Fouque, P.-A., Stern, J.: Cryptanalysis of SFLASH with slightly modified parameters. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 264–275. Springer, Heidelberg (2007). http://dx.doi.org/10.1007/978-3-540-72540-4_15 CrossRef

12.

Faugere, J.C.: A new efficient algorithm for computing gröbner bases (f 4). J. Pure Appl. Algebra 139(1), 61–88 (1999)CrossRefMathSciNetMATH

13.

Faugère, J.C.: A new efficient algorithm for computing gröbner bases without reduction to zero (f5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC 2002, pp. 75–83. ACM, New York (2002). http://doi.acm.org/10.1145/780506.780516

14.

Faugère, J.-C., Joux, A.: Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 44–60. Springer, Heidelberg (2003). http://dx.doi.org/10.1007/978-3-540-45146-4_3 CrossRef

15.

Gaborit, P. (ed.): PQCrypto 2013. LNCS, vol. 7932. Springer, Heidelberg (2013). http://dx.doi.org/10.1007/978-3-642-38616-9 MATH

16.

Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998). http://dx.doi.org/10.1007/BFb0054868 CrossRef

17.

Kipnis, A., Patarin, J., Goubin, L.: Unbalanced oil and vinegar signature schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592. Springer, Heidelberg (1999). http://dx.doi.org/10.1007/3-540-48910-X_15

18.

Kipnis, A., Shamir, A.: Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 19–30. Springer, Heidelberg (1999). http://dx.doi.org/10.1007/3-540-48405-1_2

19.

Matsumoto, T., Imai, H.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988). http://dx.doi.org/10.1007/3-540-45961-8_39

20.

McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep. 42(44), 114–116 (1978)

21.

Patarin, J.: Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt 1988. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 248–261. Springer, Heidelberg (1995). http://dx.doi.org/10.1007/3-540-44750-4_20

22.

Patarin, J.: Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996). http://dx.doi.org/10.1007/3-540-68339-9_4

23.

Patarin, J., Goubin, L., Courtois, N.T.: \(C_-+^*\) and HM: variations around two schemes of T. Matsumoto and H. Imai. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 35–50. Springer, Heidelberg (1998). http://dx.doi.org/10.1007/3-540-49649-1_4

24.

Porras, J., Baena, J., Ding, J.: ZHFE, a new multivariate public key encryption scheme. In: Mosca, M. (ed.) PQCrypto 2014. LNCS, vol. 8772, pp. 229–245. Springer, Heidelberg (2014). http://dx.doi.org/10.1007/978-3-319-11659-4_14

25.

Shamir, A.: Efficient signature schemes based on birational permutations. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 1–12. Springer, Heidelberg (1994). http://dx.doi.org/10.1007/3-540-48329-2_1

26.

Smith-Tone, D.: Properties of the discrete differential with cryptographic applications. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 1–12. Springer, Heidelberg (2010). http://dx.doi.org/10.1007/978-3-642-12929-2_1 CrossRef

27.

Tao, C., Diene, A., Tang, S., Ding, J.: Simple matrix scheme for encryption. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 231–242. Springer, Heidelberg (2013). http://dx.doi.org/10.1007/978-3-642-38616-9_16 CrossRef

28.

Thomae, E.: About the security of multivariate quadratic public key schemes. Ph.D. thesis, Ruhr-Universität Bochum (2013)

29.

Thomae, E., Wolf, C.: Cryptanalysis of enhanced TTS, STS and all its variants, or: why cross-terms are important. In: Mitrokotsa, A., Vaudenay, S. (eds.) AFRICACRYPT 2012. LNCS, vol. 7374, pp. 188–202. Springer, Heidelberg (2012). http://dx.doi.org/10.1007/978-3-642-31410-0_12 CrossRef

30.

Wiedemann, D.H.: Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theor. 32(1), 54–62 (1986)CrossRefMathSciNetMATH

31.

Wolf, C., Braeken, A., Preneel, B.: On the security of stepwise triangular systems. Des. Codes Crypt. 40(3), 285–302 (2006). http://dx.doi.org/10.1007/s10623-006-0015-5 CrossRefMathSciNetMATH

32.

Wolf, C., Preneel, B.: Taxonomy of public key schemes based on the problem of multivariate quadratic equations. In: IACR Cryptology ePrint Archive 2005, p. 77 (2005). http://eprint.iacr.org/2005/077

Titel: Extension Field Cancellation: A New Central Trapdoor for Multivariate Quadratic Systems
verfasst von: Alan Szepieniec
Jintai Ding
Bart Preneel
Verlag: Springer International Publishing
Buch: Post-Quantum Cryptography
Print ISBN: 978-3-319-29359-2

Electronic ISBN: 978-3-319-29360-8

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-29360-8_12

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"