| Fast and Secure Key Generation for Low Rank Parity Check Codes Cryptosystems
|Carlos Aguilar-Melchor, ISAE-Supaero, France; Nicolas Aragon, Victor Dyseryn, Philippe Gaborit, Université de Limoges, France
|D3-S4-T4: Key Generation & Agreement I
|Wednesday, 14 July, 23:00 - 23:20
|Wednesday, 14 July, 23:20 - 23:40
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.