Paper 2016/1065

Revisiting the Efficient Key Generation of ZHFE

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

Abstract

ZHFE, proposed by Porras at el. 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^{2¥omega+1})$ by Baena et al. to $O(n^{¥omega+3})$, where $n$ is the number of variables and $2<¥omega<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 is the best appropriate for the ZHFE scheme.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Contact author(s)
y-ikematsu @ imi kyushu-u ac jp
History
2016-11-15: received
Short URL
https://ia.cr/2016/1065
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1065,
      author = {Yasuhiko Ikematsu and Dung H.  Duong and Albrecht Petzoldt and Tsuyoshi Takagi},
      title = {Revisiting the Efficient Key Generation of ZHFE},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1065},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1065}},
      url = {https://eprint.iacr.org/2016/1065}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.