Key Recovery Attack for ZHFE

Published

June 4, 2017

Author(s)

Daniel Cabarcas, Daniel Smith-Tone, Javier A. Verbel

Abstract

At PQCRYPTO 2014, Porras, Baena and Ding introduced ZHFE, an interesting new technique for multivariate post-quantum encryption. The scheme is a generalization of HFE in which a single low degree polynomial in the central map is replaced by a pair of high degree degree polynomials with a low degree cubic polynomial contained in the ideal they generate. ZHFE was constructed with the philosophy that a statistically injective multivariate expansion map may have less rigid a structure than a bijection, and may be more resistant to cryptanalysis. We show that in the case of ZHFE, this intuition is false. We present a practical key recovery attack for ZHFE based on the independent discoveries of the low rank property of ZHFE by Verbel and by Perlner and Smith-Tone. Thus, although the two central maps of ZHFE have high degree, their low rank property makes ZHFE vulnerable to the Kipnis-Shamir(KS) rank attack.We adapt the minors modeling approach to the KS attack pioneered by Bettale, Faugere and Perret in application to HFE, and break ZHFE for practical parameters. Speci cally, our attack recovers a private key for ZHFE(7; 55; 105) in approximately 2⁶⁴ operations.

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_17

Local Download

Keywords

Multivariate public key cryptography, encryption schemes, ZHFE

Citation

Cabarcas, D. , Smith-Tone, D. and Verbel, J. (2017), Key Recovery Attack for ZHFE, PQCrypto 2017: The Eighth International Conference on Post-Quantum Cryptography, Utrecht, NL, [online], https://doi.org/10.1007/978-3-319-59879-6_17, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=926000 (Accessed May 1, 2026)

Additional citation formats