Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Key Recovery Attack for All Parameters of HFE-

Published

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 252 . Even more convincingly, the complexity of key recovery for HFE Challenge-2, an HFE (16,36,4352,4) scheme, is feasible, costing around 267 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

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 June 14, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created June 3, 2017, Updated October 12, 2021