Key Recovery Attack for ZHFE

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 polynomials with a low degree cubic polynomial contained in the ideal they generate. We present a 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 KS attack pioneered by Bettale, Faugere and Perret in application to HFE, and asymptotically break ZHFE.