The decoding problem is fundamental in post-quantum cryptography. It can be broadly described as essentially solving a linear system with a non-linear constraint on the solution. Phrased this way, the problem applies to both code-based and lattice-based cryptography. For example, the linear system may be defined over FF_q, with the non-linear constraint being a condition on the Hamming weight of the solution (McEliece, BIKE, HQC, Wave, SDitH…) or even a condition on the subfield in which the solution resides (CROSS). The system may also be defined over FF_q^m, with the non-linear constraint being a condition on the rank of the vector space spanned by the solution vectors (Mirath, Ryde). In lattice-based cryptography, the system is generally defined over ZZ_q, with the non-linear constraint being a condition on the Euclidean length of the solution (Kyber, Falcon, Dilithium, Hawk…). The list above is far from exhaustive and can extend to other areas such as Fully Homomorphic Encryption (FHE) or the blind code recognition problem (reverse of telecomunication).

For a long time in cryptography, codes and lattices evolved in parallel without much interaction. A unified approach allows for a better understanding of new cryptosystems and their fundamental limits. Whether designing or attacking, it is interesting for each field to draw inspiration from the other.

Combinatorial techniques for solving the decoding problem (in both codes and lattices) can be classified into two categories: primal attacks and dual attacks. Primal attacks aim to recover a set of information about the solution, essentially a compressed description of the solution. Exhaustive search can then be accelerated using techniques like the Birthday Paradox (collision search). More recently, techniques based on nearest-neighbor searches have emerged and significantly sped up primal attacks. The nearest-neighbor problem involves finding close pairs in a list. The notion of closeness can be extended to adapt to the non-linear constraint of the original decoding problem. However, this requires adapting known techniques to these different variants of the nearest-neighbor problem.

It turns out that primal decoding techniques are often more effective when there are few equations in the system relative to the number of unknowns. Therefore, when the number of equations is close to the number of unknowns, is it possible to reduce the problem to another decoding problem where the number of equations is smaller? One approach to this is to dualize the decoding problem: instead of searching for a solution in a specific subspace, could we reduce the problem to finding a solution in the orthogonal/dual subspace? Some recent attacks, known as dual attacks, offer an initial attempt at such a reduction. However, dual attacks are a topic of controversy. In particular, the recent dual attack by Matzov, which claims to significantly lower the security level of Kyber, a lattice-based cryptosystem currently being standardized by NIST, has not been widely accepted. The analysis behind this attack relies on a set of assumptions that, in certain scenarios, have been shown to contradict established theorems or well-tested heuristics. Nonetheless, we present new techniques for analyzing dual attacks. Specifically, we avoid the same independence assumption made in Matzov’s work, allowing us to reassess the complexity of dual attacks on Kyber and demonstrate that its security levels fall below the NIST requirements.