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.
Category / Keywords: public-key cryptography / HFE, Gr\"{o}bner basis, multivariate public key cryptosystem Date: received 28 Dec 2008 Contact author: by at crypto tw Available format(s): PDF | BibTeX Citation Version: 20081229:161921 (All versions of this report) Short URL: ia.cr/2008/543 Discussion forum: Show discussion | Start new discussion