Revisiting the efficient key generation of ZHFE

Authors

Yasuhiko Ikematsu, Kyushu UniversityFollow
Dung Hoang Duong, Kyushu UniversityFollow
Albrecht Petzoldt, Kyushu University
Tsuyoshi Takagi, Kyushu University

RIS ID

131086

Publication Details

Ikematsu, Y., Duong, D. H., Petzoldt, A. & Takagi, T. (2017). Revisiting the efficient key generation of ZHFE. Lecture Notes in Computer Science, 10194 195-212. Codes, Cryptology and Information Security Second International Conference, C2SI 2017, Rabat, Morocco, April 10-12, 2017, Proceedings - In Honor of Claude Carlet

Abstract

ZHFE, proposed by Porras et al. at PQCrypto’14, is one of the very few existing multivariate encryption schemes and a very promising candidate for post-quantum cryptosystems. The only one drawback is its slow key generation. At PQCrypto’16, Baena et al. proposed an algorithm to construct the private ZHFE keys, which is much faster than the original algorithm, but still inefficient for practical parameters. Recently, Zhang and Tan proposed another private key generation algorithm, which is very fast but not necessarily able to generate all the private ZHFE keys. In this paper we propose a new efficient algorithm for the private key generation of the ZHFE scheme. Our algorithm reduces the complexity from O(n^2w+1) by Baena et al. to O(n^w+3) , where n is the number of variables and 2<wal.’s ones. This makes our algorithm be the best appropriate for the ZHFE scheme.