Paper 2003/089
Efficient Public Key Generation for Multivariate Cryptosystems
Christopher Wolf
Abstract
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
Metadata
- Available format(s)
-
PDF
PS
- Category
- Implementation
- 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.
- Keywords
- public-key cryptographyimplementationcomplexity theoryimplementationpublic-key cryptographyHFEHidden Field Equations
- Contact author(s)
- Christopher Wolf @ esat kuleuven ac be
- History
- 2005-08-06: last of 2 revisions
- 2003-05-07: received
- See all versions
- Short URL
- https://ia.cr/2003/089
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2003/089,
author = {Christopher Wolf},
title = {Efficient Public Key Generation for Multivariate Cryptosystems},
howpublished = {Cryptology {ePrint} Archive, Paper 2003/089},
year = {2003},
url = {https://eprint.iacr.org/2003/089}
}
