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 ZHFE

Published

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 264 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

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 April 17, 2024)
Created June 3, 2017, Updated October 12, 2021