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.
Category / Keywords: implementation / public-key cryptography, implementation, complexity theory, implementation, public-key cryptography, HFE, Hidden Field Equations Publication Info: 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. Date: received 5 May 2003, last revised 6 Aug 2005 Contact author: Christopher Wolf at esat kuleuven ac be Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20050806:144941 (All versions of this report) Short URL: ia.cr/2003/089 Discussion forum: Show discussion | Start new discussion