Authors | M. Øygarden, P. Felke, H. Raddum and C. Cid |
Title | Cryptanalysis of the Multivariate Encryption Scheme EFLASH |
Afilliation | Cryptography |
Project(s) | Simula UiB, Quantum safe cryptography for the Internet of Things |
Status | Published |
Publication Type | Proceedings, refereed |
Year of Publication | 2020 |
Conference Name | RSA Conference Cryptographers' Track 2020 |
Volume | 12006 |
Pagination | 85-105 |
Date Published | 02/2020 |
Publisher | Springer |
Place Published | Lecture Notes in Computer Science |
ISBN Number | 978-3-030-40186-3 |
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. |
Citation Key | 27134 |