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 $\mathrm{GF}(31)$. To be precise, our preliminary THFE implementation is $15\times$--$20\times$ the speed of RSA-1024.

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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2008/543}},
      url = {https://eprint.iacr.org/2008/543}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.