Mckeycutter: A High-throughput Key Generator of Classic McEliece on Hardware

Classic McEliece is a code-based quantum-resistant public-key scheme characterized with relative high encapsulation/decapsulation speed and small ciphertexts, with an in-depth analysis on its security. However, slow key generation with large public key size make it hard for wider applications. Based on this observation, Mckeycutter, a high-throughput key generator in hardware, is proposed to accelerate the key generation in Classic McEliece based on algorithm-hardware co-design. Meanwhile the storage overhead caused by large-size keys is also minimized. First, compact large-size GF(2) Gauss elimination is presented by adopting naive processing array, singular matrix detection-based early abort, and memory-friendly scheduling strategy. Second, an optimized constant-time hardware sorter is proposed to support regular memory accesses with less comparators and storage. Third, algorithm-level pipeline is enabled for high-throughput processing, allowing for concurrent key generation based on decoupling between data access and computation Our FPGA implementation results achieve around 4× improvements in throughput with 9∼14× less memory-time product compared with the existing FPGA solutions.