Efficient Decryption Architecture for Classic McEliece

Xinyuan Qiao, Suwen Song, Jing Tian, Zhongfeng Wang
Nanjing University


As one of the candidates evaluated in the process of the National Institute of Standards and Technology (NIST) post-quantum cryptography standardization, the Classic McEliece, is being widely studied for its strong security. In the existing decryption architectures, the Goppa decoder is logic resource intensive, and the fast Fourier transform (FFT) unit limits its achievable frequency. In this paper, a novel folded Goppa decoder based on enhanced parallel inversionless Berlekamp-Massey (ePiBM) algorithm is proposed for complexity reduction, and a two-dimensional optimization is adopted to eliminate the frequency bottleneck caused by the FFT unit. In addition, for the finite field inversion, which is a commonly used operation in decryption, an even power-based computation scheme is presented to reduce the cost of logic resources. Based on these optimizations, a complete decryption architecture is finally developed and implemented on the Altera Stratix V FPGA. Experimental results show that the proposed decryption processor can reduce up to 37.6% logic resources and save the decryption time by up to 33.3% over the prior art.