Paper 2019/1160
Cryptanalysis of the Multivariate Encryption Scheme EFLASH
Morten Øygarden, Patrick Felke, Håvard Raddum, and Carlos Cid
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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- 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 - History
- 2019-10-07: received
- Short URL
- https://ia.cr/2019/1160
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/1160,
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},
url = {https://eprint.iacr.org/2019/1160}
}
