Small Odd Prime Field Multivariate PKCs.
Anna Inn-Tung Chen, Ming-Syan Chen⋆, Tien-Ren Chen, Chen-Mou Cheng, Jíntai Ding, Eric Li-Hsiang Kuo, Frost Li, Bo‐Yin Yang · 2008
Abstract. We show that Multivariate Public Key Cryptosystems (MP-KCs) 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 F 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. Keywords: Gröbner basis, multivariate public key cryptosystem, TTS, rainbow, HFE, ℓIC, SSE2, vector instructions