Paper 2008/498

Small Odd Prime Field Multivariate PKCs

Anna Chen, Ming-Shing Chen, Tien-Ren Chen, Chen-Mou Cheng, Jintai Ding, Eric Kuo, Frost Li, and Bo-Yin Yang


We show that Multivariate Public Key Cryptosystems (MPKCs) over fields of small odd prime characteristic, say 31, can be highly efficient. Indeed, at the same design security of $2^{80}$ under the best known attacks, odd-char MPKC is generally faster than prior MPKCs over \GF{2^k}, which are in turn faster than ``traditional'' alternatives. This seemingly counter-intuitive feat is accomplished by exploiting the comparative over-abundance of small integer arithmetic resources in commodity hardware, here embodied by SSE2 or more advanced special multimedia instructions on modern x86-compatible CPUs. We explain our implementation techniques and design choices in implementing our chosen MPKC instances modulo small a odd prime. The same techniques are also applicable in modern FPGAs which often contains a large number of multipliers.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
multivariate public key
Contact author(s)
by @ crypto tw
2008-12-31: revised
2008-12-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anna Chen and Ming-Shing Chen and Tien-Ren Chen and Chen-Mou Cheng and Jintai Ding and Eric Kuo and Frost Li and Bo-Yin Yang},
      title = {Small Odd Prime Field Multivariate PKCs},
      howpublished = {Cryptology ePrint Archive, Paper 2008/498},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.