Key Recovery Attack for ZHFE

Published: June 04, 2017

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
Pub Type: Conferences

Keywords

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