Optimizing the Key-Pair Generation Phase of McEliece Cryptosystem

Quantum computers are no longer ideas but concrete devices. They could represent a threat for public key cryptography; therefore, in 2017 NIST initiated a process to evaluate and standardize a number of quantum-resistant cryptographic algorithms. Some of these algorithms handle large size keys that may cause a reduction of performances in specific contexts. In this paper, we investigate the possibility to speed up the key-pair generation phase of McEliece cryptosystem. Taking advantage of improved polynomial multiplication in field of characteristic 2, remodelling matrices and handling cache in a clever way, it is possible to speed up the generation phase of private and public keys, paying a negligible amount of memory.