In 2016, the American National Institute of Standards and Technology (NIST) announced a call for standardization of post-quantum cryptosystems, that is cryptosystems that would be safe against an adversary equiped with a quantum computer. Among the 69 proposals that the NIST juged "complete and proper", 23 rely on the hardness of problems from coding theory, in particular the syndrome decoding problem. We are currently at the second round of the standardization process and 7 of the 17 public-key encryption system still in competition are based on codes. It is therefore very important to understand the complexity of the underlying mathematical problems.
At the second round, 7 code-based submissions have been selected:
The Syndrome Decoding problem was proven NP-complete in 1978 by Berlekamp, McEliece and van Tilborg [BMT78]. The search problem can be reduced to the corresponding decision problem, as proven in [FS96]. The complexity of the best algorithms solving this problem remains exponential in the weight of the error.
In 1962 Prange [Pra62] proposed a first algorithm called Information Set Decoding (ISD) in order to solve the syndrome decoding problem. The idea is to look for error-free information sets where to solve a linear system. Lots of improvements of the original ISD algorithm have been published [Ste88, LB88, Dum91, BJMM12, MO15], for instance using the birthday paradox in the search for collisions in lists of syndromes.
References:
Please note that this is NOT an exhaustive list of references. If you want to contribute by proposing a more detailed bibliography, please contact us.
Are there other such post-quantum cryptanalytic challenge competitions? Yes, this work was inspired by other similar initiatives and we are thankful to their authors. Concerning code-based cryptography, there exists a cryptanalytic challenge for wild McEliece organized by Daniel J. Bernstein, Tanja Lange, and Christiane Peters since 2013. We encourage you to take a look at it. There are also similar projects concerning other fields of post-quantum crypto:
The Gilbert-Varshamov distance \( d_{\rm GV}(n,k) \) for binary codes is the smallest integer \( d \) such that $$ \sum_{j=0}^{d-1} \binom{n}{j} \ge 2^{n-k}. $$