AuthorsM. Øygarden, P. Felke, H. Raddum and C. Cid
TitleCryptanalysis of the Multivariate Encryption Scheme EFLASH
AfilliationCryptography
Project(s)Simula UiB
StatusPublished
Publication TypeProceedings, refereed
Year of Publication2020
Conference NameRSA Conference Cryptographers' Track 2020
Volume12006
Pagination85-105
Date Published02/2020
Publisher Springer
Place PublishedLecture Notes in Computer Science
ISBN Number978-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 Key27134

Contact person