Matthieu Lequesne – Recovering short secret keys of RLCE in polynomial time

The security of most modern public key encryption algorithms (such as RSA) relies on arithmetic problems. Today, the hardness of these problems is threatened by the potential emergence of large quantum computers. For this reason, cryptographers try to come up with new cryptographic schemes relying on families of problems which remain hard to solve even with a quantum computer. One possible solution is to use the hardness of decoding a random error-correcting code. This field is known as code-based cryptography. This idea was introduced by McEliece in 1978 and his proposal is still considered secure today. However, McEliece’s scheme needs large public keys (about 1MB for 256 security bits), which makes it unfit for most use-cases. Therefore, there are several attempts to replace the Goppa codes, used by McEliece, with other families of codes, to obtain shorter keys. In this work, we analyze a proposal from Wang, named Random Linear Code-based Encryption (RLCE), and conclude that for all the short key parameters proposed by the author, we can recover the secret key in polynomial time, by using the dimension of the square code as a distinguisher. This is a joint work with Alain Couvreur and Jean-Pierre Tillich.

https://webconference.unicaen.fr/b/mor-7jm-rcy