Documentation

The NIST standardization process

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.

The NIST code-based candidates

At the second round, 7 code-based submissions have been selected:

• BIKE: uses quasi-cyclic MDPC codes;
• Classic McEliece: uses binary Goppa codes, following original proposition of McEliece;
• HQC: uses quasi-cyclic codes and BCH codes;
• LEDAcrypt: uses quasi-cyclic LDPC codes;
• NTS-KEM: uses binary Goppa codes;
• ROLLO: uses LRPC codes (rank-metric);
• RQC: uses ideal codes and Gabidulin codes (rank-metric).

Theoretical hardness of decoding problems

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:

• [Pra62] Eugene Prange. The use of information sets in decoding cyclic codes. In: IRE Transactions on Information Theory 8.5 (1962), p. 5-9.
• [BMT78] Elwyn Berlekamp, Robert McEliece and Henk van Tilborg. On the inherent intractability of certain coding problems. In: IEEE Trans. Inform. Theory 24.3 (1978), p. 384-386.
• [Ste88] Jacques Stern. A method for finding codewords of small weight. In: Coding Theory and Applications. Ed: G. D. Cohen and J. Wolfmann. T. 388. LNCS. Springer, 1988, p. 106-113.
• [LB88] Pil J. Lee and Ernest F. Brickell. An Observation on the Security of McEliece's Public-Key Cryptosystem. In: Advances in Cryptology - EUROCRYPT'88. T. 330. LNCS. Springer, 1988, p. 275-280.
• [Dum91] Ilya Dumer. On minimum distance decoding of linear codes. In: Proc. 5th Joint Soviet-Swedish Int. Workshop Inform. Theory. Moscow, 1991, p. 50_52.
• [FS96] Jean-Bernard Fischer, and Jacques Stern. An efficient pseudo-random generator provably as secure as syndrome decoding. In: International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 1996.
• [BJMM12] Anja Becker, Antoine Joux, Alexander May and Alexander Meurer. Decoding Random Binary Linear Codes in 2^{n/20}: How 1 + 1 = 0 Improves Information Set Decoding. In: Advances in Cryptology - EUROCRYPT 2012. LNCS. Springer, 2012.
• [MO15] Alexander May and Ilya Ozerov. "On computing nearest neighbors with applications to decoding of binary linear codes." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2015.

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.

Similar challenges

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. Another set of challenges has been proposed by researchers of the Technology Innovation Institute: The TII McEliece Challenges. We encourage you to take a look at it.

There are also similar projects concerning other fields of post-quantum crypto:

• For lattice-based cryptography:
  • The TU Darmstadt Lattice Challenge;
  • The SVP Challenge;
  • The Ideal Lattice Challenge;
  • The LWE Challenge.
• For multivariate cryptography:
  • the Fukuoka MQ Challenge.

If you know of other such challenges that are not listed here, please contact us.

Indication of complexity

For some challenges, an approximation of the theoretical complexity is given as tooltip. This number is computed by multiplying the length \(n\) by the workfactor of Dumer's algorithm for the parameters of the challenge. The workfactor is computed with the Cawof software. This value is only given for informational purposes. It does not mean that this is the real complexity of the challenge.

The Gilbert-Varshamov distance

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}. $$

Latest news