Odd-Char Multivariate Hidden Field Equations

Chia-Hsin Owen Chen IIS, Academia Sinica, Taipei, Taiwan Ming-Shing Chen IIS, Academia Sinica, Taipei, Taiwan Jintai Ding Dept. of Math. Sci., University of Cincinnati, Cincinnati, Ohio Fabian Werner Dept. of Comp. Sci., Technische Universität Darmstadt, Germany Bo-Yin Yang Dept. of Math. Sci., University of Cincinnati, Cincinnati, Ohio

TBD mathscidoc:2207.43103

IACR Cryptol. ePrint Arch., 2008.12
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 GF(31). To be precise, our preliminary THFE implementation is 15x--20x the speed of RSA-1024.
No keywords uploaded!
[ Download ] [ 2022-07-21 14:31:00 uploaded by dingjt ] [ 17 downloads ] [ 0 comments ]
@inproceedings{chia-hsin2008odd-char,
  title={Odd-Char Multivariate Hidden Field Equations},
  author={Chia-Hsin Owen Chen, Ming-Shing Chen, Jintai Ding, Fabian Werner, and Bo-Yin Yang},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220721143100437440685},
  booktitle={IACR Cryptol. ePrint Arch.},
  year={2008},
}
Chia-Hsin Owen Chen, Ming-Shing Chen, Jintai Ding, Fabian Werner, and Bo-Yin Yang. Odd-Char Multivariate Hidden Field Equations. 2008. In IACR Cryptol. ePrint Arch.. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220721143100437440685.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved