[Resource Topic] 2003/089: Efficient Public Key Generation for Multivariate Cryptosystems

Welcome to the resource topic for 2003/089

Efficient Public Key Generation for Multivariate Cryptosystems

Authors: 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

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.

ePrint: https://eprint.iacr.org/2003/089

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .