Skip to main content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Key Recovery Attack for ZHFE

Published

Author(s)

Daniel Cabarcas, Daniel C. 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, -1
Conference Title
PQCrypto 2017: The Eighth International Conference on Post-Quantum Cryptography

Keywords

Multivariate public key cryptography, encryption schemes, ZHFE
Created June 4, 2017, Updated November 10, 2018