Post-quantum cryptography

Motivation:
Introduction
Quantum computing
Cryptography:
Hash-based
Code-based
Lattice-based
MQ

Cryptanalytic challenges for wild McEliece

The following text is from Daniel J. Bernstein, Tanja Lange, and Christiane Peters, the authors of "Wild McEliece Incognito."
Update: Some solutions have been submitted by Grégory Landais and Nicolas Sendrier. We are processing the solutions.

The challenges

We have created a spectrum of cryptanalytic challenges as a way to measure and focus progress in attacking the "wild McEliece" cryptosystem and the "wild McEliece incognito" cryptosystem. Each challenge consists of a public key and a ciphertext; we challenge the readers to find matching plaintext or even to find the secret keys.

For each cryptosystem, challenges are indexed by field size and by key size. We will keep this site up to date to report

  • any solutions (plaintexts) sent to us---with credit to the first solver of each challenge, and with as much detail as the solver is willing to provide regarding how the challenge was cryptanalyzed;
  • any secret keys sent to us---with credit to the first solver of each challenge, and with as much detail as the solver is willing to provide regarding how the challenge was cryptanalyzed;
  • cryptanalytic benchmarks---measurements of the speed of publicly available cryptanalytic software for the smaller challenges, as a way for the community to verify and demonstrate improvements in attack algorithms; and
  • predictions---estimates of how difficult the larger challenges will be to break.

The challenge generator

We wrote a script wild.sage that works with the Sage computer-algebra system. This script is a reference implementation of the McEliece cryptosystem, including wild McEliece, including wild McEliece incognito. The implementation generates a random secret key and public key, encrypts a random plaintext (Niederreiter-style), decrypts the ciphertext, and checks for a match. It prints the public key and ciphertext. All of the challenges here were generated by this script. Usage example:
     sage wild.sage 13 3 451 24 2
The arguments are q, m, n, s, t; see the paper for definitions.

Wild McEliece

Field sizeKilobytes in public key (link to challenge)
2 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 128 136 144 152 160 168 176 184 192
3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176 184
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176 184 192 200 208
5 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176 184
7 4 5 6 7 8 9 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160
8 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176
9 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176 184 192
11 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124
13 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136
16 3 4 5 18 19 20 21 22 23 24 25 26 27 28 29 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152
17 3 4 5 6 7 23 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152
19 3 4 5 6 7 8 9 10 11 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160
23 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176
25 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 116 120 124 128 136 144 152 160 168 176 184
27 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 168 176 184
29 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34
31 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46
32 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42

Wild McEliece incognito

Field sizeKilobytes in public key (link to challenge)
3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176 184
4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176 184 192 200 208
5 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176 184
7 4 5 6 7 8 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168
8 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176 184
9 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176 184 192 200
11 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128
13 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136
16 3 4 5 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152
17 3 4 5 6 7 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160
19 3 4 5 6 7 8 9 10 11 12 13 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168
23 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176
25 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 40 104 108 112 116 120 124 128 136 144 152 160 168 176 184
27 22 25 29 30 32 34 38 40 44 46 50 52 54 56 58 60 64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124 128 136 144 152 160 168 176 184 192
29 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62
31 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72
32 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 68 72 76 80

Version

This is version 2013.02.06 of the wild-challenges.html web page.