Implementing 128-Bit Secure MPKC Signatures

Ming-Shing CHEN  Wen-Ding LI  Bo-Yuan PENG  Bo-Yin YANG  Chen-Mou CHENG  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.3   pp.553-569
Publication Date: 2018/03/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.553
Type of Manuscript: PAPER
Category: Cryptography and Information Security
MPKC signatures,  finite field arithmetic,  SIMD,  additive FFT,  

Full Text: PDF(2.1MB)
>>Buy this Article

Multivariate Public Key Cryptosystems (MPKCs) are often touted as future-proofing against Quantum Computers. In 2009, it was shown that hardware advances do not favor just “traditional” alternatives such as ECC and RSA, but also makes MPKCs faster and keeps them competitive at 80-bit security when properly implemented. These techniques became outdated due to emergence of new instruction sets and higher requirements on security. In this paper, we review how MPKC signatures changes from 2009 including new parameters (from a newer security level at 128-bit), crypto-safe implementations, and the impact of new AVX2 and AESNI instructions. We also present new techniques on evaluating multivariate polynomials, multiplications of large finite fields by additive Fast Fourier Transforms, and constant time linear solvers.