Rank metric is a very promising research direction for code-based cryptography. In fact, thanks to the high complexity of generic decoding attacks against codes in this metric, it is possible to easily select parameters that yield very small data sizes. In this paper we analyze cryptosystems based on Low-Rank Parity-Check (LRPC) codes, one of the classes of codes that are efficiently decodable in the rank metric. We show how to exploit the decoding failure rate, which is an inherent feature of these codes, to devise a reaction attack aimed at recovering the private key. As a case study, we cryptanalyze the recent McNie submission to NIST’s Post-Quantum Standardization process. Additionally, we provide details of a simple implementation to validate our approach.

Cryptographic primitives from coding theory are some of the most promising candidates for NIST’s Post-Quantum Cryptography Standardization process. In this paper, we introduce a variety of techniques to improve operations on dyadic matrices, a particular type of symmetric matrices that appear in the automorphism group of certain linear codes. Besides the independent interest, these techniques find an immediate application in practice. In fact, one of the candidates for the Key Exchange functionality, called DAGS, makes use of quasi-dyadic matrices to provide compact keys for the scheme.

The most important pre-quantum threat to AES-128 is the 1994 van Oorschot–Wiener parallel rho method, a low-communication parallel pre-quantum multi-target preimage-search algorithm. This algorithm uses a mesh of p small processors, each running for approximately $2^{128}/pt$ fast steps, to find one of $t$ independent AES keys $k_1$, …, $k_t$, given the ciphertexts AES_k_1(0), …,AES_k_t(0) for a shared plaintext $0$. NIST has claimed a high post-quantum security level for AES-128, starting from the following rationale: Grover’s algorithm requires a long-running serial computation, which is difficult to implement in practice. In a realistic attack, one has to run many smaller instances of the algorithm in parallel, which makes the quantum speedup less dramatic. NIST has also stated that resistance to multi-key attacks is desirable; but, in a realistic parallel setting, a straightforward multi-key application of Grover’s algorithm costs more than targeting one key at a time. This paper introduces a different quantum algorithm for multi-target preimage search. This algorithm shows, in the same realistic parallel setting, that quantum preimage search benefits asymptotically from having multiple targets. The new algorithm requires a revision of NIST’s AES-128, AES-192, and AES-256 security claims.