Revisiting the efficient key generation of ZHFE

Yasuhiko Ikematsu, Dung H. Duong, Albrecht Petzoldt, Tsuyoshi Takagi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


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(n2ω+1) by Baena et al. to O(nω+3), where n is the number of variables and 2 <ω<3 is a linear algebra constant. We also estimate the number of possible keys generated by all existing private key generation algorithms for ZHFE. Our algorithm generates as many private ZHFE keys as the original and Baena et al.’s ones. This makes our algorithm be the best appropriate for the ZHFE scheme.

Original languageEnglish
Title of host publicationCodes, Cryptology and Information Security - 2nd International Conference, C2SI 2017, Proceedings In Honor of Claude Carlet
EditorsAbderrahmane Nitaj, Said El Hajji, El Mamoun Souidi
PublisherSpringer Verlag
Number of pages18
ISBN (Print)9783319555881
Publication statusPublished - 2017
Event2nd International Conference on Codes, Cryptology and Information Security, C2SI 2017 - Rabat, Morocco
Duration: Apr 10 2017Apr 12 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10194 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other2nd International Conference on Codes, Cryptology and Information Security, C2SI 2017
City Rabat

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Revisiting the efficient key generation of ZHFE'. Together they form a unique fingerprint.

Cite this