Paper 2019/1160

Cryptanalysis of the Multivariate Encryption Scheme EFLASH

Morten Øygarden, Patrick Felke, Håvard Raddum, and Carlos Cid


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
multivariate cryptographycryptanalysisGröbner basis
Contact author(s)
carlos cid @ rhul ac uk
morten oygarden @ simula no
haavardr @ simula no
patrick felke @ hs-emden-leer de
2019-10-07: received
Short URL
Creative Commons Attribution


      author = {Morten Øygarden and Patrick Felke and Håvard Raddum and Carlos Cid},
      title = {Cryptanalysis of the Multivariate Encryption Scheme EFLASH},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1160},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.