Evaluation of Gaussian elimination using HLS for fast public key generation in the Classic McEliece

Abstract

With the recent development of quantum computers and massively parallel computing, the continued use of existing cryptographic techniques is in jeopardy. For this reason, standardization of Post-Quantum Cryptography (PQC) is underway at the National Institute of Standards and Technology (NIST) in the United States and other national standardization organizations. While several cryptosystems have already been finalized as part of the standard, there are still proposals under discussion, including the Classic McEliece Cryptosystem, which is the only code-based cipher remaining in the U.S. NIST proposal. The characteristic feature of the Classic McEliece Cryptosystem is its very large key size, with a maximum public key size of approximately 1.4 MB. Generating a public key requires a very large matrix calculation. Because of the large size of the matrix, the time required for generation is also large, and even after optimization, it is the most time-consuming process. In this paper, we propose an FPGA implementation of the Gaussian elimination method to accelerate the generation of public keys for the Classic McEliece Cryptosystem using HLS. By implementing the method on an FPGA for data centers suitable for HLS, the CPU load can be reduced, and the public key can be obtained from the FPGA. As a result of the implementation, the processing time was about 0.1 seconds per operation with the largest parameter size. Since the speed was about the same as the calculation on a partially optimized CPU, parallelization of this calculation can be expected to result in faster key generation.