Paper 2008/543
Odd-Char Multivariate Hidden Field Equations
Chia-Hsin Owen Chen, Ming-Shing Chen, Jintai Ding, Fabian Werner, and Bo-Yin Yang
Abstract
We present a multivariate version of Hidden Field Equations (HFE)
over a finite field of odd characteristic, with an extra
``embedding'' modifier. Combining these known ideas makes our new
MPKC (multivariate public key cryptosystem) more efficient
and scalable than any other extant multivariate encryption scheme.
Switching to odd characteristics in HFE-like schemes affects how an
attacker can make use of field equations. Extensive empirical tests
(using MAGMA-2.14, the best commercially available \mathbold{F_4}
implementation) suggests that our new construction is indeed secure
against algebraic attacks using Gröbner Basis algorithms. The
``embedding'' serves both to narrow down choices of pre-images and
to guard against a possible Kipnis-Shamir type (rank-based) attack. We
may hence reasonably argue that for practical sizes, prior attacks
take exponential time.
We demonstrate that our construction is in fact efficient by
implementing practical-sized examples of our ``odd-char HFE'' with 3
variables (``THFE'') over
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- HFEGröbner basismultivariate public key cryptosystem
- Contact author(s)
- by @ crypto tw
- History
- 2008-12-29: received
- Short URL
- https://ia.cr/2008/543
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2008/543, author = {Chia-Hsin Owen Chen and Ming-Shing Chen and Jintai Ding and Fabian Werner and Bo-Yin Yang}, title = {Odd-Char Multivariate Hidden Field Equations}, howpublished = {Cryptology {ePrint} Archive, Paper 2008/543}, year = {2008}, url = {https://eprint.iacr.org/2008/543} }