Key Recovery Attack for All Parameters of HFE-

Published

June 4, 2017

Author(s)

Jeremy Vates, Daniel Smith-Tone

Abstract

Recently, by an interesting confluence, multivariate schemes with the minus modifier have received attention as candidates for multivariate encryption. Among these candidates is the twenty year old HFE^– scheme originally envisioned as a possible candidate for both encryption and digital signatures, depending on the number of public equations removed. HFE has received a great deal of attention and a variety of cryptanalyses over the years; however, HFE^– has escaped these assaults. The direct algebraic attack that broke HFE Challenge I is provably more complex on HFE^– , and even after two decades HFE Challenge II is daunting, though not achieving a security level we may find acceptable today. The minors modeling approach to the Kipnis-Shamir (KS) attack is very efficient for HFE, but fails when the number of equations removed is greater than one. Thus it seems reasonable to use HFE^– for encryption with two equations removed. This strategy may not be quite secure, however, as our new approach shows. We derive a new key recovery attack still based on the minors modeling approach that succeeds for all parameters of HFE^–. The attack is polynomial in the degree of the extension, though of higher degree than the original minors modeling KS-attack. As an example, the complexity of key recovery for HFE^– (q=31,n=36,D=1922,a=2) is 2⁵² . Even more convincingly, the complexity of key recovery for HFE Challenge-2, an HFE^– (16,36,4352,4) scheme, is feasible, costing around 2⁶⁷ operations. Thus, the parameter choices for HFE^– for both digital signatures and, particularly, for encryption must be re-examined.

Volume

10346

Conference Dates

June 26-28, 2017

Conference Location

Utrecht, NL

Conference Title

PQCrypto 2017: The Eighth International Conference on Post-Quantum Cryptography

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-319-59879-6_16

Local Download

Keywords

Multivariate cryptography, HFE, Encryption, MinRank, Q-rank

Citation

Vates, J. and Smith-Tone, D. (2017), Key Recovery Attack for All Parameters of HFE-, PQCrypto 2017: The Eighth International Conference on Post-Quantum Cryptography, Utrecht, NL, [online], https://doi.org/10.1007/978-3-319-59879-6_16, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=925999 (Accessed April 26, 2024)