This article discusses the security of McEliece-like encryption schemes using subspace subcodes of Reed–Solomon codes,i.e.subcodes of Reed–Solomon codes over${\mathbb {F}_{q^{m}}}$whose entries lie in a fixed collection of${\mathbb {F}_{q}}$–subspaces of${\mathbb {F}_{q^{m}}}$. These codes appear to be a natural generalisation of Goppa and alternant codes and provide a broader flexibility in designing code based encryption schemes. For the security analysis, we introduce a new operation on codes called thetwisted productwhich yields a polynomial time distinguisher on such subspace subcodes as soon as the chosen${\mathbb {F}_{q}}$–subspaces have dimension larger than$m/2$. From this distinguisher, we build an efficient attack which in particular breaks some parameters of a recent proposal due to Khathuria, Rosenthal and Weger.

The key encapsulation mechanism EDON-K was proposed in response to the call for post-quantum cryptography standardization issued by the National Institute of Standards and Technologies (NIST). This scheme is inspired by the McEliece scheme but uses another family of codes defined over F2128instead of F2and is not based on the Hamming metric. It allows significantly shorter public keys than the McEliece scheme. In this paper, we give a polynomial time algorithm that recovers the encapsulated secret. This attack makes the scheme insecure for the intended use. We obtain this result by observing that recovering the error in the McEliece scheme corresponding to EDON-K can be viewed as a decoding problem for the rank-metric. We show that the code used in EDON-K is in fact a super-code of a Low Rank Parity Check (LRPC) code of very small rank (1 or 2). A suitable parity-check matrix for the super-code of such low rank can be easily derived from for the public key. We then use this parity-check matrix in a decoding algorithm that was devised for LRPC codes to recover the error. Finally we explain how we decapsulate the secret once we have found the error.