## CryptoDB

### Paper: Odd-Char Multivariate Hidden Field Equations

Authors: Chia-Hsin Owen Chen Ming-Shing Chen Jintai Ding Fabian Werner Bo-Yin Yang URL: http://eprint.iacr.org/2008/543 Search ePrint Search Google 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\"obner 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.
##### BibTeX
@misc{eprint-2008-18174,
title={Odd-Char Multivariate Hidden Field Equations},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / HFE,  Gr\"{o}bner basis, multivariate public key cryptosystem},
url={http://eprint.iacr.org/2008/543},
note={ by@crypto.tw 14241 received 28 Dec 2008},
author={Chia-Hsin Owen Chen and Ming-Shing Chen and Jintai Ding and Fabian Werner and Bo-Yin Yang},
year=2008
}