Fast and Secure Key Generation for Low Rank Parity Check Codes Cryptosystems

Among the candidates for NIST's post-quantum cryptography standardization project, cryptosystems that rely on Low Rank Parity Check (LRPC) codes have interesting properties, such as a low public key size. However, the key generation phase for these cryptosystems is computationally expensive when done in constant-time, which is a security requirement on the standardization project, making it almost unusable for ephemeral key generation. We present a new constant-time algorithm for key generation on LRPC code-based cryptosystems, that divides the computational costs by four when compared to previous work over ROLLO, one of the NIST candidates. Our improvement consists in changing the way objects of a quotient ring are represented. By switching from a canonical basis to an optimal normal basis, we enable the full potential of the Itoh-Tsuiji algorithm for field inversion.