TY - GEN
T1 - Revisiting the efficient key generation of ZHFE
AU - Ikematsu, Yasuhiko
AU - Duong, Dung H.
AU - Petzoldt, Albrecht
AU - Takagi, Tsuyoshi
N1 - Funding Information:
This work was supported by CREST, JST. The second author also acknowledges the Japanese Society for the Promotion of Science (JSPS) for financial support under grant KAKENHI 16K17644.
Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85015256282&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85015256282&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-55589-8_13
DO - 10.1007/978-3-319-55589-8_13
M3 - Conference contribution
AN - SCOPUS:85015256282
SN - 9783319555881
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 195
EP - 212
BT - Codes, Cryptology and Information Security - 2nd International Conference, C2SI 2017, Proceedings In Honor of Claude Carlet
A2 - Nitaj, Abderrahmane
A2 - El Hajji, Said
A2 - Souidi, El Mamoun
PB - Springer Verlag
T2 - 2nd International Conference on Codes, Cryptology and Information Security, C2SI 2017
Y2 - 10 April 2017 through 12 April 2017
ER -