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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
multivariate public key
Contact author(s)
by @ crypto tw
History
2008-12-31: revised
2008-12-02: received
See all versions
Short URL
https://ia.cr/2008/498
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/498,
      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{https://eprint.iacr.org/2008/498}},
      url = {https://eprint.iacr.org/2008/498}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.