Abstract
EFLASH is a multivariate public-key encryption scheme proposed by Cartor and Smith-Tone at SAC 2018. In this paper we investigate the hardness of solving the particular equation systems arising from EFLASH, and show that the solving degree for these types of systems is much lower than estimated by the authors. We show that a Gröbner basis algorithm will produce degree fall polynomials at a low degree for EFLASH systems. In particular we are able to accurately predict the number of these polynomials occurring at step degrees 3 and 4 in our attacks. We performed several experiments using the computer algebra system MAGMA, which indicate that the solving degree is at most one higher than the one where degree fall polynomials occur; moreover, our experiments show that whenever the predicted number of degree fall polynomials is positive, it is exact. Our conclusion is that EFLASH does not offer the level of security claimed by the designers. In particular, we estimate that the EFLASH version with 80-bit security parameters offers at most 69 bits of security.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The authors call this the degree of regularity, but are in fact describing the first fall degree.
References
Bardet, M., Faugère, J.-C., Salvy, B.: Complexity of Gröbner basis computation for Semi-regular overdetermined sequences over \({{\mathbb{F}}_{2}}\) with solutions in \({{\mathbb{F}}_{2}}\). [Research Report] RR-5049, INRIA, inria-00071534 (2003)
Bardet, M., et al.: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. In: Proceedings of MEGA, vol. 5 (2005)
Bettale, L., Faugère, J.-C., Perret, L.: Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic. Des. Codes Cryptogr. 69(1), 1–52 (2013). https://doi.org/10.1007/s10623-012-9617-2
Bouillaguet, C., Fouque, P.-A., Macario-Rat, G.: Practical key-recovery for all possible parameters of SFLASH. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 667–685. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_36
Cabarcas, D., Smith-Tone, D., Verbel, J.A.: Key recovery attack for ZHFE. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 289–308. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_17
Cartor, R., Smith-Tone, D.: EFLASH: a new multivariate encryption scheme. In: Cid, C., Jacobson Jr., M. (eds.) SAC 2018. Lecture Notes in Computer Science, vol. 11349, pp. 281–299. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-10970-7_13
Chen, M.-S., Yang, B.-Y., Smith-Tone, D.: PFLASH - secure asymmetric signatures on smart cards. In: Lightweight Cryptography Workshop (2015). https://ws680.nist.gov/publication/get_pdf.cfm?pub_id=926103
Cox, D.A., Little, J., O’shea, D.: Using Algebraic Geometry, vol. 185. Springer, New York (2006). https://doi.org/10.1007/b138611
Diene, A., Ding, J., Gower, J.E., Hodges, T.J., Yin, Z.: Dimension of the linearization equations of the matsumoto-imai cryptosystems. In: Ytrehus, Ø. (ed.) WCC 2005. LNCS, vol. 3969, pp. 242–251. Springer, Heidelberg (2006). https://doi.org/10.1007/11779360_20
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). https://doi.org/10.1007/978-3-642-22792-9_41
Ding, J., Kleinjung, T.: Degree of regularity for HFE-. In: IACR Cryptology ePrint Archive 2011, p. 570 (2011)
Ding, J., Schmidt, D.: Solving degree and degree of regularity for polynomial systems over a finite fields. In: Fischlin, M., Katzenbeisser, S. (eds.) Number Theory and Cryptography. LNCS, vol. 8260, pp. 34–49. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42001-6_4
Ding, J., Dubois, V., Yang, B.-Y., Chen, O.C.-H., Cheng, C.-M.: Could SFLASH be repaired? In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 691–701. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70583-3_56
Faugère, J.C.: A new efficient algorithm for computing Gröbner bases (F4). J. Pure Appl. Algebra 139(1–3), 61–88 (1999)
Faugère, J.C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F 5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, pp. 75–83. ACM (2002)
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). https://doi.org/10.1007/978-3-540-45146-4_3
Felke, P.: On the affine transformations of HFE-cryptosystems and systems with branches. In: Ytrehus, Ø. (ed.) WCC 2005. LNCS, vol. 3969, pp. 229–241. Springer, Heidelberg (2006). https://doi.org/10.1007/11779360_19
Felke, P.: On the security of biquadratic \(C^{*}\) public-key cryptosystems and its generalizations. Crypt. Commun. 11, 1–16 (2018)
Joux, A., Vitse, V.: A crossbred algorithm for solving boolean polynomial systems. In: Kaczorowski, J., Pieprzyk, J., Pomykała, J. (eds.) NuTMiC 2017. LNCS, vol. 10737, pp. 3–21. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76620-1_1
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). https://doi.org/10.1007/3-540-48405-1_2
Liu, J., et al.: Structural key recovery of simple matrix encryption scheme family. Comput. J. 61 (2018). https://doi.org/10.1093/comjnl/bxy093
Matsumoto, T., Imai, H.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: Barstow, D., et al. (eds.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-45961-8_39
Patarin, J.: Cryptanalysis of the matsumoto and imai public key scheme of Eurocrypt’88. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 248–261. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-44750-4_20
Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_4
Patarin, J., Courtois, N., Goubin, L.: FLASH, a fast multivariate signature algorithm. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 298–307. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45353-9_22
Perlner, R., Petzoldt, A., Smith-Tone, D.: Total break of the SRP encryption scheme. In: Adams, C., Camenisch, J. (eds.) SAC 2017. LNCS, vol. 10719, pp. 355–373. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-72565-9_18
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). https://doi.org/10.1007/978-3-319-11659-4_14
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). https://doi.org/10.1007/978-3-642-38616-9_16
Yasuda, T., Sakurai, K.: A multivariate encryption scheme with rainbow. In: Qing, S., Okamoto, E., Kim, K., Liu, D. (eds.) ICICS 2015. LNCS, vol. 9543, pp. 236–251. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29814-6_19
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Øygarden, M., Felke, P., Raddum, H., Cid, C. (2020). Cryptanalysis of the Multivariate Encryption Scheme EFLASH. In: Jarecki, S. (eds) Topics in Cryptology – CT-RSA 2020. CT-RSA 2020. Lecture Notes in Computer Science(), vol 12006. Springer, Cham. https://doi.org/10.1007/978-3-030-40186-3_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-40186-3_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-40185-6
Online ISBN: 978-3-030-40186-3
eBook Packages: Computer ScienceComputer Science (R0)