International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Small Odd Prime Field Multivariate PKCs

Anna Chen an Ming-Shing Chen
Tien-Ren Chen
Chen-Mou Cheng
Jintai Ding
Eric Kuo
Frost Li
Bo-Yin Yang
Search ePrint
Search Google
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.
  title={Small Odd Prime Field Multivariate PKCs},
  booktitle={IACR Eprint archive},
  keywords={implementation / multivariate public key},
  note={ 14244 received 26 Nov 2008, last revised 31 Dec 2008},
  author={Anna Chen an Ming-Shing Chen and Tien-Ren Chen and Chen-Mou Cheng and Jintai Ding and Eric Kuo and Frost Li and Bo-Yin Yang},