Skip to main content
placeholder image

An efficient key generation of ZHFE public key cryptosystem

Journal Article


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 and estimate the number of possible keys generated by all existing private key generation algorithms for the ZHFE scheme. Our algorithm generates as many private ZHFE keys as the original and Baena et al.'s ones and reduces the complexity from O(n2ω+1) by Baena et al. to O(nω+3), where n is the number of variables and ω is a linear algebra constant. Moreover, we also analyze when the decryption of the ZHFE scheme does not work.

UOW Authors


  •   Ikematsu, Yasuhiko (external author)
  •   Duong, Dung Hoang.
  •   Petzoldt, Albrecht (external author)
  •   Takagi, Tsuyoshi (external author)

Publication Date


  • 2018

Geographic Focus


Citation


  • Ikematsu, Y., Duong, D., Petzoldt, A. & Takagi, T. (2018). An efficient key generation of ZHFE public key cryptosystem. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E101A (1), 29-38.

Scopus Eid


  • 2-s2.0-85040177459

Number Of Pages


  • 9

Start Page


  • 29

End Page


  • 38

Volume


  • E101A

Issue


  • 1

Place Of Publication


  • Japan

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 and estimate the number of possible keys generated by all existing private key generation algorithms for the ZHFE scheme. Our algorithm generates as many private ZHFE keys as the original and Baena et al.'s ones and reduces the complexity from O(n2ω+1) by Baena et al. to O(nω+3), where n is the number of variables and ω is a linear algebra constant. Moreover, we also analyze when the decryption of the ZHFE scheme does not work.

UOW Authors


  •   Ikematsu, Yasuhiko (external author)
  •   Duong, Dung Hoang.
  •   Petzoldt, Albrecht (external author)
  •   Takagi, Tsuyoshi (external author)

Publication Date


  • 2018

Geographic Focus


Citation


  • Ikematsu, Y., Duong, D., Petzoldt, A. & Takagi, T. (2018). An efficient key generation of ZHFE public key cryptosystem. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E101A (1), 29-38.

Scopus Eid


  • 2-s2.0-85040177459

Number Of Pages


  • 9

Start Page


  • 29

End Page


  • 38

Volume


  • E101A

Issue


  • 1

Place Of Publication


  • Japan