nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Key Recovery Attack for ZHFE

verfasst von : Daniel Cabarcas, Daniel Smith-Tone, Javier A. Verbel

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

At PQCRYPTO 2014, Porras, Baena and Ding introduced ZHFE, an interesting new technique for multivariate post-quantum encryption. The scheme is a generalization of HFE in which a single low degree polynomial in the central map is replaced by a pair of high degree polynomials with a low degree cubic polynomial contained in the ideal they generate. We present a key recovery attack for ZHFE based on the independent discoveries of the low rank property of ZHFE by Verbel and by Perlner and Smith-Tone. Thus, although the two central maps of ZHFE have high degree, their low rank property makes ZHFE vulnerable to the Kipnis-Shamir (KS) rank attack. We adapt KS attack pioneered by Bettale, Faugère and Perret in application to HFE, and asymptotically break ZHFE.

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 Key Recovery Attack for All Parameters of HFE-

Nächstes Kapitel Post-quantum RSA

Nur mit Berechtigung zugänglich

Baena, J.B., Cabarcas, D., Escudero, D.E., Porras-Barrera, J., Verbel, J.A.: Efficient ZHFE key generation. In: Takagi [27], pp. 213–232. http://dx.doi.org/10.1007/978-3-319-29360-8_14

Bettale, L., Faugère, J.C., Perret, L.: Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic. Des. Codes Crypt. 69(1), 1–52 (2013)MathSciNetCrossRefMATH

Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system I. The user language. J. Symbolic Comput. 24(3–4), 235–265 (1997). http://dx.doi.org/10.1006/jsco.1996.0125, computational algebra and number theory (London, 1993)MathSciNetCrossRefMATH

Cartor, R., Gipson, R., Smith-Tone, D., Vates, J.: On the differential security of the HFEV- signature primitive. In: Takagi [27], pp. 162–181. http://dx.doi.org/10.1007/978-3-319-29360-8_11

Chen, M.S., Yang, B.Y., Smith-Tone, D.: PFLASH - secure asymmetric signatures on smart cards. In: Lightweight Cryptography Workshop 2015 (2015). http://csrc.nist.gov/groups/ST/lwc-workshop.2015/papers/session3-smith-tone-paper.pdf

Daniels, T., Smith-Tone, D.: Differential properties of the HFE cryptosystem. In: Mosca [20] , pp. 59–75. http://dx.doi.org/10.1007/978-3-319-11659-4_4

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., Petzoldt, A., Wang, L.: The cubic simple matrix encryption scheme. In: Mosca [20], pp. 76–87. http://dx.doi.org/10.1007/978-3-319-11659-4_5

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

10.

Ding, J., Yang, B.Y.: Degree of regularity for HFEV and HFEV. In: Gaborit [15], pp. 52–66. http://dx.doi.org/10.1007/978-3-642-38616-9

11.

Dubois, V., Gama, N.: The degree of regularity of HFE systems. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 557–576. Springer, Heidelberg (2010). http://dx.doi.org/10.1007/978-3-642-17373-8_32 CrossRef

12.

Faugère, J.C., Din, M.S.E., Spaenlehauer, P.J.: Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree: algorithms and complexity. J. Symbolic Comput. 46(4), 406–437 (2011)MathSciNetCrossRefMATH

13.

Faugère, J.C., El Din, M.S., Spaenlehauer, P.J.: Computing loci of rank defects of linear matrices using gröbner bases and applications to cryptology. In: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ISSAC 2010, pp. 257–264. ACM, New York (2010)

14.

Faugère, J.-C., Gligoroski, D., Perret, L., Samardjiska, S., Thomae, E.: A polynomial-time key-recovery attack on MQQ cryptosystems. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 150–174. Springer, Heidelberg (2015). http://dx.doi.org/10.1007/978-3-662-46447-2_7

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.

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

17.

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). doi:10.1007/3-540-48405-1_2 CrossRef

18.

Moody, D., Perlner, R.A., Smith-Tone, D.: An asymptotically optimal structural attack on the ABC multivariate encryption scheme. In: Mosca [20], pp. 180–196. http://dx.doi.org/10.1007/978-3-319-11659-4_11

19.

Moody, D., Perlner, R.A., Smith-Tone, D.: Key recovery attack on the cubic ABC simple matrix multivariate encryption scheme. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 289–308. Springer, Cham (2017)

20.

Mosca, M. (ed.): PQCrypto 2014. LNCS, vol. 8772. Springer, Cham (2014). http://dx.doi.org/10.1007/978-3-319-11659-4 MATH

21.

Patarin, J., Courtois, N., Goubin, L.: QUARTZ, 128-bit long digital signatures. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 282–297. Springer, Heidelberg (2001). http://dx.doi.org/10.1007/3-540-45353-9_21 CrossRef

22.

Perlner, R.A., Smith-Tone, D.: A classification of differential invariants for multivariate post-quantum cryptosystems. In: Gaborit [15], pp. 165–173. http://dx.doi.org/10.1007/978-3-642-38616-9

23.

Perlner, R.A., Smith-Tone, D.: Security analysis and key modification for ZHFE. In: Takagi[27], pp. 197–212. http://dx.doi.org/10.1007/978-3-319-29360-8_13

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, Cham (2014). doi:10.1007/978-3-319-11659-4_14

25.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999). (electronic)MathSciNetCrossRefMATH

26.

Smith-Tone, D.: On the differential security of multivariate public key cryptosystems. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 130–142. Springer, Heidelberg (2011). doi:10.1007/978-3-642-25405-5_9 CrossRef

27.

Takagi, T. (ed.): PQCrypto 2016. LNCS, vol. 9606. Springer, Cham (2016). http://dx.doi.org/10.1007/978-3-319-29360-8 MATH

28.

Tao, C., Diene, A., Tang, S., Ding, J.: Simple matrix scheme for encryption. In: Gaborit [15], pp. 231–242. http://dx.doi.org/10.1007/978-3-642-38616-9

29.

Verbel, J.A.: Efficiency and security of ZHFE. Master’s thesis, Universidad Nacional de Colombia, Sede Medellín (2016)

30.

Zhang, W., Tan, C.H.: On the security and key generation of the ZHFE encryption scheme. In: Ogawa, K., Yoshioka, K. (eds.) IWSEC 2016. LNCS, vol. 9836, pp. 289–304. Springer, Cham (2016). doi:10.1007/978-3-319-44524-3_17 CrossRef

Titel: Key Recovery Attack for ZHFE
verfasst von: Daniel Cabarcas
Daniel Smith-Tone
Javier A. Verbel
Verlag: Springer International Publishing
Buch: Post-Quantum Cryptography
Print ISBN: 978-3-319-59878-9

Electronic ISBN: 978-3-319-59879-6

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-59879-6_17

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"

Premium Partner