Paper 2003/089

Efficient Public Key Generation for Multivariate Cryptosystems

Christopher Wolf


Asymmetric cryptographic systems using multivariate polynomials over finite fields have been proposed several times since the 1980s. Although some of them have been successfully broken, the area is still vital and promises interesting algorithms with low computational costs, short message, and signature sizes. In this paper, we present two novel strategies ``base transformation" and ``adapted evaluation" for the generation of the public key in such schemes. We demonstrate both at the example of the Hidden Field Equations (HFE) system and outline how they can be adapted to similar systems. In addition, we compare the running time of the previously known technique ``polynomial interpolation" with our new developments both from a theoretical perspective and by empirical studies. These experiments confirm our theoretical studies, namely, base transformation is faster than polynomial interpolation. Especially the first step is $O(n^2)$ while it is $O(n^4)$ for polynomial interpolation where $n$ denotes the number of variables. Moreover, the running time of polynomial interpolation is approximately 30\% higher than for base transformation.

Available format(s)
Publication info
Published elsewhere. This is a preliminary version of the article ``Efficient public key generation for HFE and variations." In Cryptographic Algorithms and Their Uses 2004, pages 78--93. Dawson, Klimm, editors, QUT University, 2004.
public-key cryptographyimplementationcomplexity theoryimplementationpublic-key cryptographyHFEHidden Field Equations
Contact author(s)
Christopher Wolf @ esat kuleuven ac be
2005-08-06: last of 2 revisions
2003-05-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christopher Wolf},
      title = {Efficient Public Key Generation for Multivariate Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2003/089},
      year = {2003},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.