menu

Technology Innovation Institute

 97,374

The TII McEliece Challenges

Contribute to data security in a post-quantum era by participating in the TII McEliece Challenge and win prizes worth $75,000

This challenge is closed

stage:
Won
prize:
$75,000

This challenge is closed

more
Summary
Leaderboard
Timeline
Updates23
Forum1
Community
Press
FAQ
Meet the Winners
Summary

Overview

The webpage is dedicated to decoding challenges inspired by the McEliece Cryptosystem. The purpose of the challenge is to understand the hardness of the problems that underlie the security of the modern versions of the McEliece Cryptosystems like Classic McEliece.

Note that you are able to sign up and submit to challenge from now until the submission deadline. To view the information for a specific instance, navigate to the Leaderboard Tab and click on the number of your chosen instance from the correct Track, then proceed to the submission form when you are ready to test your solution.

Track One: McEliece Key Recovery Challenge

Track one of the challenges focuses on McEliece key recovery attacks, i.e., recovering the secret key from a given public key. The McEliece public key is constructed as follows:

Set integer parameters \(n>1\)\(1 < t < n\)\(m>1\).

The parameter \(n\) defines the length of the Goppa code, \(m\) defines a finite field extension \(\mathbb{F}_{2^m} \cong \mathbb{F}_{2}[x]/(f)\) for some \(f\) irreducible over \(\mathbb{F}_{2}\).

Let \(V: \mathbb{F}_{2^m} \rightarrow \mathbb{F}_2^m\) be the bijection that represents \(\mathbb{F}_{2^m}\) as an \(m\)-dimensional vector space over \(\mathbb{F}_2\), i.e, \(\sum_{i=0}^{m-1} a_i \gamma^i \mapsto [a_0, \ldots, a_{m-1}]\), where \(\gamma\) is a primitive root of \(f\).

Choose at random a vector \(L = \{\alpha_1, \ldots, \alpha_n\} \subset \mathbb{F}_{2^m}\).

Choose an irreducible polynomial \(g \in \mathbb{F}_{2^m}[x]\) of degree \(t\).

Consider \(\overline{H}_{\mathsf{Goppa}}(L,g) \in \mathbb{F}_{2^m}^{t \times n}\) of the form 

 

\[\overline{H}_{\mathsf{Goppa}}(L,g) =      \begin{pmatrix}     1 & 1 & \ldots & 1 \\     \alpha_1 & \alpha_2 & \ldots & \alpha_{n} \\     \vdots & \vdots & \ddots & \vdots \\  \alpha_1^{t-1} & \alpha_2^{t-1} & \ldots & \alpha_{n}^{t-1}     \end{pmatrix}    \cdot      \begin{pmatrix}     g^{-1}(\alpha_1) & 0 & \ldots & 0 \\  0 & g^{-1}(\alpha_2) & \ldots & 0 \\     \vdots & \vdots & \ddots & \vdots \\     0 & 0 & \ldots & g^{-1}(\alpha_n)     \end{pmatrix}\]

From \(\overline{H}_{\mathsf{Goppa}}(L,g) \in \mathbb{F}_{2^m}^{t \times n}\), construct the matrix \(H_{\mathsf{Goppa}}(L,g) \in\mathbb{F}_{2}^{tm \times n}\) by applying the bijection \(V\) to each element of \(\overline{H}_{\mathsf{Goppa}}(L,g)\).

If \(H_{\mathsf{Goppa}}(L,g) \in\mathbb{F}_{2}^{tm \times n}\) is not full-rank, restart from choosing a new vector \(L\).

Apply row-echelon form to \(H_{\mathsf{Goppa}}(L,g) \in\mathbb{F}_{2}^{tm \times n}\) to obtain the public matrix \(H_\textrm{pub}\). It serves as McEliece's public key.

The corresponding key recovery problem is defined as follows.

Problem 1 (McEliece Key Recovery): Given a matrix \(H_\textrm{pub} \in \mathbb{F}_{2}^{tm \times n}\) constructed as above, recover \(g\) and \(L\).

Track 1A: Theoretical Key Recovery – 10.000$

We are welcoming new theoretical results in algorithms, both classical and quantum, for Track 1A. The submission should be typed in LaTeX and submitted in PDF format via the submission form button above. Please follow the Springer Lecture Notes in Computer Science (LNCS) style. There are no other restrictions on the format; however, the reviewers are not obliged to read all of your pdf, so brevity will be helpful in your submission. You may also submit your paper simultaneously to any other conference or venue.

Track 1B: Practical Key Recovery – 10.000$

We also provide practical key recovery challenges. Each challenge set contains the following data

  • public matrix \(H_\textrm{pub}\) in the systematic form (the identity matrix is also stored),
  • coefficients of unitary irreducible polynomial \(f\) s.t. \(\mathbb{F}_{2^m} \cong \mathbb{F}_{2}[x]/(f)\).

The task is to recover the secret polynomial \(g\) and the vector \(L\). The challenges are ordered by their hardness, ranging from 22 to 255 bits of complexity. Only one prize winner will be awarded in each track, and the prize amount will be determined by how high the winner scores on their track's leaderboard. See the Prize section below for more information.

Track Two: Message Recovery Challenge

In McEliece, cryptosystem messages (or keys in McEliece KEM) are binary vectors of size \(n\) and Hamming weight \(t\). For the public matrix \(H_ \textrm{pub} \in \mathbb{F}_{2}^{tm \times n}\), the ciphertext for the message \(\mathbf{m}\) is its syndrome, namely 

\[\mathbf{c} = H_ \textrm{pub}\mathbf{m}.\]

The message recovery problem relies on the hardness of syndrome decoding for binary Goppa codes. In particular,
 

Problem 2 (McEliece Message Recovery): Given a matrix \(H_ \textrm{pub} \in \mathbb{F}_{2}^{m \times n}\) and the syndrome \(\mathbf{c} = H_  \textrm{pub}\mathbf{m}\), find \(\mathbf{m}\).

Track two focuses on practical message recovery attacks. Each challenge set contains the following data:

  • public matrix \(H_  \textrm{pub}\) in the systematic form (the identity matrix is also stored),
  • syndrome vector \(\mathbf{c} \in \mathbb{F}_2^{mt}\),
  • coefficients of unitary irreducible polynomial \(f\) s.t. \(\mathbb{F}_{2^m} \cong \mathbb{F}_{2}[x]/(f)\).

The task is to recover the message \(\mathbf{m}\).

For testing purposes, we provide toy examples with bit securities in the range 20–32. There is no prize associated with those toy challenges. The actual challenges range in complexity from 34–74 and 75-90 bits of security.
 

Track 2A: Practical Message Recovery – 15.000$

This track consists of seven different prize levels that are correlated with bit complexity, ranging from 34 to 74. Only one prize winner will be awarded in each track, and the prize amount will be determined by how high the winner scores on their track's leaderboard. See the Prize section below for more information. The security levels are chosen so that the lower levels may be completed reasonably with existing techniques. But the highest levels are designed such that current state-of-the-art algorithms (with slight tweaks) are able to solve these instances, if enough computational resources are available. Improvements to your chosen algorithm will be essential for achieving the full prize in these challenges.

Track 2B: Practical Message Recovery – 40.000$

This track consists of sixteen different challenges with a bit complexity of 75–90. The security levels are chosen such that it is unlikely that current state-of-the-art algorithms without algorithmic improvements are able to solve these instances. See the Prize section below for more information.

 

Background

The McEliece cryptosystem remains, despite significant cryptanalytic efforts, a secure scheme since its invention in 1978. Further, it counts as post-quantum secure, i.e., there are no efficient quantum algorithms known that solve the underlying hard problems. These two facts led to the McEliece scheme being a fourth-round candidate of the current NIST PQC standardization effort for post-quantum secure schemes, in the form of the Classic McEliece submission.

In order to ensure a precise understanding of the security with respect to today's computational resources and algorithmic advancements, we launched the TII McEliece Challenges. This challenge aims at covering all aspects of McEliece security, especially also those, which have received less attention in the past years. Before detailing the precise challenges and choices, let us outline a simplified version of the McEliece scheme.

The McEliece Scheme

McEliece is a code-based scheme, that is based on the hardness of decoding specific linear codes. Therefore, the private key is a structured parity-check matrix \(H\) of a linear code, where McEliece relies on binary Goppa codes. The known structure of the matrix \(H\) allows to correct up to \(t\) errors efficiently. That means for a given syndrome \(\mathbf{c}\), it is possible to efficiently find a vector \(\mathbf{m}\) of Hamming-weight \(t\), satisfying \(H\mathbf{m} = \mathbf{c}\), if such a vector exists.

The public key of the scheme is a permuted and “scrambled” version of \(H_{\mathsf{Goppa}}\). Therefore one first applies a permutation \(P\) to the columns of \(H\) and then performs a basis change via multiplication with an invertible matrix \(S\) to obtain the public key \(H_\textrm{pub}=SH_{\mathsf{Goppa}}(L,g)P\). The matrices \(S\) and \(P\) are part of the secret key.

A message \(\mathbf{m}\), which is a vector with Hamming-weight \(t\), is then encrypted by calculating the syndrome \(\mathbf{c} = H_ \textrm{pub}\mathbf{m}\). Now \(\mathbf{c}\) is the corresponding ciphertext. For decryption, the receiver first calculates \(S^{-1} \mathbf{c} = HP\mathbf{m}\) and then recovers \(P\mathbf{m}\) via the efficient decoding algorithm. Eventually \(\mathbf{m}\) is recovered by applying the inverse permutation to \(P\mathbf{m}\).

The Security Foundation

The security of the McEliece scheme relies on two different problems. First, to ensure that only the holder of the secret key is able to efficiently correct \(t\) errors, i.e., is able to decrypt, it must be hard to recover the hidden structure of the matrix \(H\) from \(H_\textrm{pub}\). This problem is known as the key-recovery problem. On the hand, to ensure that a ciphertext hides the message, it must be hard to compute \(\mathbf{m}\) from \(\mathbf{c}\) without knowing the secret key, i.e., when only \(\mathbf{c}\) and \(H_\textrm{pub}\) are known. This problem is known as the message-recovery problem.

In contrast to many other schemes, for McEliece, the two problems of message- and key-recovery are fundamentally different. The problem that determines parameters of the scheme is the message recovery problem. That means algorithms to solve this problem are more efficient than those recovering the secret key. The best algorithms for message recovery in the case of McEliece are generic decoding algorithms, namely Information Set Decoding (ISD) algorithms. These algorithms are generic in the sense that they can be used to decode any random (appearing) code, and they do not exploit any specifics of the binary Goppa code used in McEliece.

For key-recovery the best-known attacks are rather simple, involving brute-force enumeration of parts of the secret key. Their complexity is far higher than those of message recovery attacks.

Challenges and Goals

We provide challenges for both fundamental problems on which the security of McEliece is based.

The far lower bit complexities of message recovery attacks have always set a higher incentive to study those than to study key recovery attacks. Our challenge aims at breaking this trend by providing its own track focusing on key-recovery attacks. This track subdivides into a theoretical (Track 1A) and a practical section (Track 1B). In the theoretical section, we are interested in classical or quantum algorithmic advancements on McEliece key recovery. These works should focus especially on the parameter regime found in secure McEliece instantiations.

Additionally, we provide a practical key recovery track (Track 1B). This track features various reduced-size instances, starting from 20-bit security up to 255-bit security. Algorithms found optimal for solving these reduced instances might differ from the most efficient for cryptographic-sized instances. However, considering the rather limited progress on key-recovery attacks, any advancement is welcome.

The TII McEliece Challenges also features message recovery attacks in its Track Two. This track aims at improving the accuracy of our today’s security understanding to especially support the parameter selection process. Again this track subdivides into a Track 2A and a Track 2B. Track 2A covers instances, which are both in range for standard techniques and for current state-of-the-art algorithms if either enough computational resources are available or smaller algorithmic improvements are leveraged. Our Track 2B then covers instances that are considered to be out of range of current algorithms. This track aims at setting an incentive for algorithmic advancements and their immediate translation to practice.


Note that we focus on the Niederreiter variant, which is also the one used in the Classic McEliece submission.

 

How do I Win?

For the Theoretical Key recovery Track, we are looking for innovative approaches that may move the McEliece system into a leading candidate for post-quantum encryption. 

For the other tracks, find yourself at the top of the leaderboard by solving the most complicated instance in your chosen track!

The submission deadline for Solutions in response to this Challenge can be viewed in the official Challenge Timeline.

 

Submission Requirements

Submissions should consist of the following:

For Theoretical Key Recovery algorithms (Track 1A):

  • Please follow the Springer Lecture Notes in Computer Science (LNCS) Template.
  • You will then submit your paper as a PDF.
    • We will also ask for an abstract of your paper and for some information about the authors/submitters of the paper.

For the Practical Approach and Message Recovery tracks (Tracks 1B, 2A, and 2B), please submit:

  • A submission title and a list of Challenge Team Members, their institutional/organizational affiliations, and their roles.
  • Your solution to the algorithm and recovered key or plaintext
  • Optionally, a write-up on Your Solution. The narrative You provide shall include the following:
    • Please include the algorithm used to generate your keys.
    • Please provide details on the hardware you used to obtain your solution.
    • Please include the runtime based on the hardware you used to obtain your solution.
    • Any other pertinent details, such as:
      • Any novel techniques that you would like to highlight.
      • Descriptions and sources of any open-source data used to aid in development/testing
      • Recommendations for further use of Your solution.

Challenge Timeline

Registration OpensMay 9, 2023
Submission Form OpensMay 23, 2023
Registration and Submission deadlineMay 8, 2024 @ 5:00pm ET
JudgingMay 8 - June 4, 2024
Winners AnnouncedJune 11, 2024

Prize

After the submission deadline, the following four prizes will be awarded to the best-judged submission in the theoretical track and to the competitor/team that has solved the most difficult instance in each of the other tracks. Note that each track will only award one winner, but that the prize level for each winner will be determined by their level on the challenge Leaderboard. In other words, if the highest solved instance belongs to a higher hardness level, the prize will also increase. This challenge was originally launched with only one prize level per track, but additional partial prize levels have now been added to provide the crowd with more opportunities to win!

  1. (1A) Best Theoretical Key Recovery Algorithms - $10,000
  2. (1B) Best Practical Key Recovery Approach - Full prize: $10,000. Partial prize will be awarded according to the graphic above, if the full prize instance levels are not met.
     
  3. (2A) Best Practical Message Recovery of 70-74-bit Encryption - Full prize: $15,000. Partial prize will be awarded according to the graphic above, if the full prize instance levels are not met.
  4. (2B) Best Practical Message Recovery of 80-94-bit Encryption - Full prize: $40,000. Partial prize will be awarded according to the graphic above, if the full prize instance levels are not met.

Judging Criteria for Theoretical Key Recovery Algorithms (Track 1A)

Section DescriptionOverall Weight
NoveltyDoes this approach represent a new method of key recovery?20%
AccuracyDoes this approach solve for S, G, and P?40%
Editorial QualityIs this paper of adequate editorial quality?10%
Scientific QualityDoes this paper contribute to the science of post-quantum cryptography?30%

 

 Please view the Official Rules below in the Challenge-Specific Agreement

Leaderboard

leaderboard

Instance
Leader
Status
A $10,000 prize for the instances listed below.
255
n/a
Available to Solve
254
n/a
Available to Solve
253
n/a
Available to Solve
252
n/a
Available to Solve
251
n/a
Available to Solve
250
n/a
Available to Solve
249
n/a
Available to Solve
248
n/a
Available to Solve
247
n/a
Available to Solve
246
n/a
Available to Solve
245
n/a
Available to Solve
244
n/a
Available to Solve
243
n/a
Available to Solve
242
n/a
Available to Solve
241
n/a
Available to Solve
240
n/a
Available to Solve
239
n/a
Available to Solve
238
n/a
Available to Solve
237
n/a
Available to Solve
236
n/a
Available to Solve
235
n/a
Available to Solve
234
n/a
Available to Solve
233
n/a
Available to Solve
232
n/a
Available to Solve
231
n/a
Available to Solve
230
n/a
Available to Solve
229
n/a
Available to Solve
228
n/a
Available to Solve
227
n/a
Available to Solve
226
n/a
Available to Solve
225
n/a
Available to Solve
224
n/a
Available to Solve
223
n/a
Available to Solve
222
n/a
Available to Solve
221
n/a
Available to Solve
220
n/a
Available to Solve
219
n/a
Available to Solve
218
n/a
Available to Solve
217
n/a
Available to Solve
216
n/a
Available to Solve
215
n/a
Available to Solve
214
n/a
Available to Solve
213
n/a
Available to Solve
212
n/a
Available to Solve
211
n/a
Available to Solve
210
n/a
Available to Solve
209
n/a
Available to Solve
208
n/a
Available to Solve
207
n/a
Available to Solve
206
n/a
Available to Solve
205
n/a
Available to Solve
204
n/a
Available to Solve
203
n/a
Available to Solve
202
n/a
Available to Solve
201
n/a
Available to Solve
200
n/a
Available to Solve
199
n/a
Available to Solve
198
n/a
Available to Solve
197
n/a
Available to Solve
196
n/a
Available to Solve
195
n/a
Available to Solve
194
n/a
Available to Solve
193
n/a
Available to Solve
192
n/a
Available to Solve
191
n/a
Available to Solve
190
n/a
Available to Solve
189
n/a
Available to Solve
188
n/a
Available to Solve
187
n/a
Available to Solve
186
n/a
Available to Solve
185
n/a
Available to Solve
184
n/a
Available to Solve
183
n/a
Available to Solve
182
n/a
Available to Solve
181
n/a
Available to Solve
180
n/a
Available to Solve
179
n/a
Available to Solve
178
n/a
Available to Solve
177
n/a
Available to Solve
176
n/a
Available to Solve
175
n/a
Available to Solve
174
n/a
Available to Solve
173
n/a
Available to Solve
172
n/a
Available to Solve
171
n/a
Available to Solve
170
n/a
Available to Solve
169
n/a
Available to Solve
168
n/a
Available to Solve
167
n/a
Available to Solve
166
n/a
Available to Solve
165
n/a
Available to Solve
164
n/a
Available to Solve
163
n/a
Available to Solve
162
n/a
Available to Solve
161
n/a
Available to Solve
160
n/a
Available to Solve
159
n/a
Available to Solve
158
n/a
Available to Solve
157
n/a
Available to Solve
156
n/a
Available to Solve
155
n/a
Available to Solve
154
n/a
Available to Solve
153
n/a
Available to Solve
152
n/a
Available to Solve
151
n/a
Available to Solve
150
n/a
Available to Solve
149
n/a
Available to Solve
148
n/a
Available to Solve
147
n/a
Available to Solve
146
n/a
Available to Solve
145
n/a
Available to Solve
144
n/a
Available to Solve
143
n/a
Available to Solve
142
n/a
Available to Solve
141
n/a
Available to Solve
140
n/a
Available to Solve
139
n/a
Available to Solve
138
n/a
Available to Solve
137
n/a
Available to Solve
136
n/a
Available to Solve
135
n/a
Available to Solve
134
n/a
Available to Solve
133
n/a
Available to Solve
132
n/a
Available to Solve
131
n/a
Available to Solve
130
n/a
Available to Solve
129
n/a
Available to Solve
128
n/a
Available to Solve
127
n/a
Available to Solve
126
n/a
Available to Solve
125
n/a
Available to Solve
124
n/a
Available to Solve
123
n/a
Available to Solve
122
n/a
Available to Solve
121
n/a
Available to Solve
120
n/a
Available to Solve
119
n/a
Available to Solve
118
n/a
Available to Solve
117
n/a
Available to Solve
115
n/a
Available to Solve
114
n/a
Available to Solve
113
n/a
Available to Solve
112
n/a
Available to Solve
111
n/a
Available to Solve
110
n/a
Available to Solve
109
n/a
Available to Solve
107
n/a
Available to Solve
106
n/a
Available to Solve
105
n/a
Available to Solve
104
n/a
Available to Solve
103
n/a
Available to Solve
102
n/a
Available to Solve
101
n/a
Available to Solve
100
n/a
Available to Solve
99
n/a
Available to Solve
97
n/a
Available to Solve
96
n/a
Available to Solve
95
n/a
Available to Solve
94
n/a
Available to Solve
93
n/a
Available to Solve
92
n/a
Available to Solve
91
n/a
Available to Solve
90
n/a
Available to Solve
89
n/a
Available to Solve
88
n/a
Available to Solve
87
n/a
Available to Solve
86
n/a
Available to Solve
85
n/a
Available to Solve
84
n/a
Available to Solve
83
Solved, But Available For Practice
Algorithm:   Brute-force key search using the support-splitting algorithm.
Hardware:   The solver was run on a variety of servers containing AMD and Ampere CPUs. As the approach is trivially parallel, the duration is given in single-core time.
Runtime:   1471:04:51:00
Comments (optional):   A paper with implementation details and a code release are forthcoming.
Instance:   83
Solution file content:  
[a^5,a^58,a^229,a^61,a^28,1]
[a^179,a^181,a^129,a^172,a^169,a^231,a^116,a^223,a^249,a^215,a^57,a^89,a^184,a^37,a^14,a^43,a^119,a^112,a^186,a^27,a^16,a^20,a^134,a^211,a^146,a^4,a^39,a^67,a^98,a^93,a^151,a^8,a^207,a^225,a^118,a^99,a^47,a^154,a^145,a^148,a^110,a^241,a^185,a^58,a^88,a^59,a^65,a^107,a^212,a^144,a^31,a^141,a^253,a^135,a^12,a^139,a^140,a^30,a^10,a^84,a^101,a^6,a^248,a^22,a^152,a^201,a^229,a^208,a^195,a^156,a^192,a^233,a^105,a^200,a^227,a^136,a^198,a^165,a^50,a^60,a^245,a^138,a^205,a^182,a^189,a^86,a^203,a^103,a^96,a^197,1,a^133,a^7,a^130,a^94,a^202,a^218,a^33,a^214,a^19,a^124,a^106,a^85,a^222,a^191,a^51,a^143,a^254,a^45,a^28,a^9,a^236,a^95,a^132,a^239,a^235,a^234,a^206,a^78,a^242,a^100,a^221,a^209,a^61,a^199,a^128,a^168,a^193,a^82,a^104,a^90,a^55,a^190,a^40,a^81,a^63,a^41,a^108,a^23,a^166,a^142,a^35,a^194,a^238,a^87,a^240,a^226,a^5,a^25,a^164,a^91,a^137,a^97,a^153,a^176,a^54,a^79,a^121,a^155,a^72,a^49,a^147,a^158,a^188,a^76,a^115,a^123,a^216,a^196,a^53,a^38,a^159,a^75,a^114,a^252,0,a^29,a^243,a^109,a^167,a^162,a^219,a^15,a^213,a^250,a^13,a^11,a^24,a^2,a^251,a,a^77,a^74,a^171,a^178,a^149,a^217,a^83,a^177,a^32,a^230,a^224,a^102,a^18,a^204,a^68,a^228,a^56,a^26,a^73,a^237,a^161,a^111,a^80,a^246,a^126,a^125,a^113,a^92,a^210,a^42,a^36,a^17,a^34,a^131,a^120,a^66,a^150,a^174,a^183,a^62,a^70,a^127,a^122,a^117,a^52,a^48,a^163,a^71,a^170,a^3,a^46,a^180,a^157,a^232,a^220,a^187,a^160,a^244,a^175,a^21,a^44,a^173]
82
n/a
Available to Solve
81
n/a
Available to Solve
80
n/a
Available to Solve
79
n/a
Available to Solve
78
n/a
Available to Solve
77
n/a
Available to Solve
76
n/a
Available to Solve
74
n/a
Available to Solve
73
n/a
Available to Solve
72
n/a
Available to Solve
71
n/a
Available to Solve
70
n/a
Available to Solve
A $7,500 prize for the instances listed below.
69
n/a
Available to Solve
68
Solved, But Available For Practice
Algorithm:  
Hardware:  
Runtime:  
Comments:  
Instance:   68
Solution file content:  
[ a^43, a^51, a^37 ]
[ 0, a^24, a^32, a^52, a^25, a^51, a^14, a^8, a^38, a^50, a^5, a^17, a^19, a^18, a^45, a^41, a^2, a^58, a^48, a^9, a^15, a^29, a^36, a^59, a^21, a^27, a^11, a^56, a^42, a^53, a^12, a^13, a^4, a, a^37, a^39, a^33, a^44, a^10, a^55, a^47, a^49, a^28, a^20, a^7, a^61, a^31, a^46, a^3, a^34, a^23, a^62, a^54 ]
66
Solved, But Available For Practice
Algorithm:   Adaptation to Goppa codes of degree r=3 of the algorithm from the article: R. Mora, "On the matrix code of quadratic relationships for a Goppa code", arXiv:2310.20497 Modeling introduced in: A. Couvreur, R. Mora, and J.-P. Tillich, "A new approach based on quadratic forms to attack the McEliece cryptosystem", Asiacrypt 2023
Hardware:   Intel Xeon E7-4850 v3
Runtime:   02:06:00:00
Comments (optional):  
Instance:   66
Solution file content:  
[ a^46, a^53, a^24, a^8 ]
[ 0, a^2, a^53, a^33, a^44, a^6, a^18, a^5, a^36, a^48, a^12, a^60, a^21, a^55, a^52, a^17, a^39, a^20, a^62, a^34, a^57, a^38, a^61, a^25, a^46, a^10, a^22, a^7, a^3, a^40, a^37, a^29, a^8, a^4, a^49, a^32, a^56, a^47, a^41, a^15, a^35, a^42, a^54, a^16, a^45, a^19, a^26, a^50, a^43, a^28, a^51, a^23, a^24, a^30, a^13, a^59 ]
65
Solved, But Available For Practice
Algorithm:  
Hardware:  
Runtime:  
Comments:  
Instance:   65
Solution file content:  
[ a^54, a^17, a ]
[ 0, a^28, a^8, a^51, a^23, a^36, a, a^14, a^5, a^25, a^33, a^52, a^55, a^40, a^37, a^35, a^10, a^22, a^53, a^3, a^15, a^24, a^20, a^13, a^57, a^18, a^47, a^43, a^7, a^60, a^21, a^58, a^16, a^4, a^29, a^41, a^59, a^32, a^26, a^38, a^45, a^11, a^9, a^49, a^48, a^31, a^61, a^6, a^27, a^50, a^30, a^17, a^46, a^12 ]
63
Solved, But Available For Practice
Algorithm:  
Hardware:  
Runtime:  
Comments:  
Instance:   63
Solution file content:  
[ a^4, a^4, a^17 ]
[ 0, a^38, a^39, a, a^31, a^36, a^32, a^58, a^44, a^10, a^42, a^52, a^37, a^3, a^62, a^47, a^6, a^30, a^17, a^34, a^8, a^29, a^57, a^51, a^26, a^25, a^5, a^60, a^16, a^59, a^53, a^15, a^14, a^43, a^4, a^22, a^12, a^61, a^11, a^35, a^23, a^2, a^9, a^41, a^45, a^24, a^28, a^48, a^40, a^56, a^20, a^50, a^7, a^54, a^18 ]
A $5,000 prize for the instances listed below.
60
Solved, But Available For Practice
Algorithm:   Adaptation to Goppa codes of degree r=3 of the algorithm from the article: R. Mora, "On the matrix code of quadratic relationships for a Goppa code", arXiv:2310.20497 Modeling introduced in: A. Couvreur, R. Mora, and J.-P. Tillich, "A new approach based on quadratic forms to attack the McEliece cryptosystem", Asiacrypt 2023
Hardware:   Intel Xeon E7-4850 v3
Runtime:   00:00:55:00
Comments (optional):  
Instance:   60
Solution file content:  
[ a^19, a^39, a^26, a^25 ]
[ 0, a^42, a^37, a^5, a^61, a^27, a^60, a^32, a^48, a^50, a^21, a^53, a^45, a^10, a^28, a^46, a^4, a^8, a^59, a^6, a^39, a, a^35, a^2, a^3, a^23, a^15, a^44, a^9, a^49, a^43, a^41, a^54, a^18, a^47, a^56, a^29, a^33, a^19, a^24, a^36, a^20, a^62, a^13, a^52, a^34, a^25, a^12, a^58, a^14, a^11, a^17, a^30, a^57, a^31, a^55, a^38, a^26 ]
59
n/a
Available to Solve
58
Solved, But Available For Practice
Algorithm:  
Hardware:  
Runtime:  
Comments:  
Instance:   58
Solution file content:  
[ a^61, a^40, a^48 ]
[ 0, 1, a^59, a^24, a^42, a^7, a^41, a^4, a^50, a^48, a^23, a^40, a^56, a^43, a^13, a^15, a^37, a^55, a^18, a^19, a^57, a^46, a^60, a^44, a^21, a^27, a^9, a^33, a^45, a^61, a^35, a^52, a^22, a^11, a^30, a^8, a^14, a^39, a^31, a^32, a^58, a^53, a, a^47, a^20, a^34, a^2, a^38, a^36, a^26, a^28, a^29, a^3, a^12, a^5, a^16, a^25 ]
57
Solved, But Available For Practice
Algorithm:   Adaptation to Goppa codes of degree r=3 of the algorithm from the article: R. Mora, "On the matrix code of quadratic relationships for a Goppa code", arXiv:2310.20497 Modeling introduced in: A. Couvreur, R. Mora, and J.-P. Tillich, "A new approach based on quadratic forms to attack the McEliece cryptosystem", Asiacrypt 2023
Hardware:   Intel Xeon E7-4850 v3
Runtime:   00:18:54:00
Comments (optional):  
Instance:   57
Solution file content:  
[ a^40, a^55, a^7, a^16 ]
[ 0, a^19, a^35, a^30, a^6, a, a^25, a^4, a^24, a^3, a^32, a^41, a^59, a^56, a^28, a^42, a^12, a^20, a^5, a^22, a^18, a^61, a^29, a^58, a^15, a^39, a^55, a^2, a^49, a^40, a^47, a^23, a^37, a^45, a^11, a^46, a^36, a^17, a^34, a^9, a^16, a^38, a^10, a^54, a^51, a^62, a^14, a^48, a^26, a^57, a^7, a^50, a^60, a^33, a^27, a^21, a^52, a^8, a^53 ]
A $2,500 prize for the instances listed below.
55
n/a
Available to Solve
53
Solved, But Available For Practice
Algorithm:   Adaptation to Goppa codes of degree r=3 of the algorithm from the article: R. Mora, "On the matrix code of quadratic relationships for a Goppa code", arXiv:2310.20497 Modeling introduced in: A. Couvreur, R. Mora, and J.-P. Tillich, "A new approach based on quadratic forms to attack the McEliece cryptosystem", Asiacrypt 2023
Hardware:   Intel Xeon E7-4850 v3
Runtime:   00:03:33:00
Comments (optional):  
Instance:   53
Solution file content:  
[ a^9, a^16, a^13, a^10 ]
[ 0, a^56, a^22, a^62, a^29, a^2, a^51, a^12, a^44, a^27, a^55, a^53, a^17, a^26, a^18, a^9, a^35, a, a^61, a^36, a^41, a^13, a^33, a^16, a^28, a^46, a^49, a^54, a^48, a^19, a^57, a^30, a^45, a^47, a^59, a^43, a^52, a^21, a^31, a^40, a^4, a^58, a^60, a^37, a^8, a^6, a^5, a^20, a^7, a^11, a^14, a^42, a^32, a^15, a^34, a^50, a^39, a^38, a^23, a^24 ]
52
n/a
Available to Solve
51
n/a
Available to Solve
A $1,000 prize for the instances listed below.
50
Solved, But Available For Practice
Algorithm:   Adaptation to Goppa codes of degree r=3 of the algorithm from the article: R. Mora, "On the matrix code of quadratic relationships for a Goppa code", arXiv:2310.20497 Modeling introduced in: A. Couvreur, R. Mora, and J.-P. Tillich, "A new approach based on quadratic forms to attack the McEliece cryptosystem", Asiacrypt 2023
Hardware:   Intel Xeon E7-4850 v3
Runtime:   00:00:44:00
Comments (optional):  
Instance:   50
Solution file content:  
[ a^35, a^7, a^19, a^30 ]
[ 0, a^56, a^30, a^33, a^9, a^43, a^51, a^10, a^37, a^29, a^6, a^27, a^28, a^15, a^38, a^41, a^8, a^62, a^22, a^32, a^21, a^24, a^3, a^54, a^31, a^53, a^5, a^48, a^50, a^2, a^25, a^34, a^58, a^46, a^7, a^23, a^49, a^47, a^12, a^45, a^35, a^52, a^20, a^39, a^40, a^19, a^13, a^36, a^14, a^16, a^26, a^4, a, a^55, a^44, a^11, a^60, a^42, a^59, a^17, a^18 ]
49
Solved, But Available For Practice
Algorithm:   Adaptation to Goppa codes of degree r=2 of the algebraic modeling from the article: J.-C. Faugère, V. Gauthier Umaña, A. Otmani, L. Perret, and J.-P. Tillich "A distinguisher for high-rate McEliece cryptosystems", IEEE Transactions on Information Theory. Hybrid approach.
Hardware:   Intel Xeon E7-4850 v3
Runtime:   00:00:59:00
Comments (optional):  
Instance:   49
Solution file content:  
[ a^11, a^14, a^12 ]
[ a^9, a^29, a^22, a^12, a^30, a^28, a^25, a^26, a^8, a, a^4, a^5, a^2, a^19, a^20, a^27, a^15, a^7, a^3, 0, a^23 ]
48
Solved, But Available For Practice
Algorithm:  
Hardware:  
Runtime:  
Comments:  
Instance:   48
Solution file content:  
[ a^59, a^37, a^57 ]
[ 0, 1, a^62, a^49, a^12, a^55, a^13, a^44, a^11, a^35, a^8, a^21, a^24, a^59, a^58, a^28, a^29, a^51, a^27, a, a^7, a^16, a^60, a^39, a^4, a^50, a^19, a^15, a^46, a^22, a^2, a^45, a^34, a^54, a^53, a^3, a^43, a^40, a^36, a^31, a^20, a^47, a^61, a^56, a^26, a^23, a^41, a^57, a^52, a^32, a^30, a^38, a^10, a^5, a^48, a^9, a^18, a^14, a^33, a^17 ]
47
Solved, But Available For Practice
Algorithm:   Adaptation to Goppa codes of degree r=2 of the algebraic modeling from the article: J.-C. Faugère, V. Gauthier Umaña, A. Otmani, L. Perret, and J.-P. Tillich "A distinguisher for high-rate McEliece cryptosystems", IEEE Transactions on Information Theory. Hybrid approach.
Hardware:   Intel Xeon E7-4850 v3
Runtime:   00:05:54:00
Comments (optional):  
Instance:   47
Solution file content:  
[ a^5, a^5, a^18 ]
[ a^11, a^18, a^23, a^13, a^25, a^14, a^15, a^6, a^28, a^30, a^19, a^29, a^27, a^22, a^7, a^4, a^9, a^12, a^2, a^26, a^16, 0, a^21 ]
46
n/a
Available to Solve
45
Solved, But Available For Practice
Algorithm:   Adaptation to Goppa codes of degree r=3 of the algorithm from the article: R. Mora, "On the matrix code of quadratic relationships for a Goppa code", arXiv:2310.20497 Modeling introduced in: A. Couvreur, R. Mora, and J.-P. Tillich, "A new approach based on quadratic forms to attack the McEliece cryptosystem", Asiacrypt 2023
Hardware:   Intel Xeon E7-4850 v3
Runtime:   00:03:10:00
Comments (optional):  
Instance:   45
Solution file content:  
[ a^16, a^25, a^28, a^55 ]
[ 0, 1, a^44, a^48, a^51, a^37, a^29, a^45, a^14, a^56, a^57, a^59, a^52, a^11, a^61, a^6, a^42, a^5, a^54, a^18, a^46, a^49, a^33, a^34, a^17, a^9, a^23, a^21,a^13, a^3, a^25, a^47, a^58, a^31, a^26, a^19, a^28, a^43, a^39, a^35, a^53, a^24, a^12, a^41, a^36, a^60, a^30, a^62, a^10, a^50, a^55, a^8, a^15, a^40, a^4, a^32, a^7, a^22, a^20, a^27, a^2, a^38 ]
44
Solved, But Available For Practice
Algorithm:  
Hardware:  
Runtime:  
Comments:  
Instance:   44
Solution file content:  
[ a^39, a^35, a^34 ]
[ 0, a^11, a^35, a^39, a^56, a^30, a^21, a^26, a^4, a^23, a^5, a^19, a^32, a^15, a^36, a^3, a, a^24, a^8, a^13, a^27, a^6, a^41, a^57, a^38, a^55, a^51, a^16, a^10, a^47, a^48, a^33, a^50, a^46, a^29, a^58, a^22, a^9, a^42, a^37, a^44, a^45, a^20, a^14, a^53, a^17, a^31, a^43, a^18, a^25, a^61, a^60, a^59, a^34, a^52, a^49, a^40, a^12, a^7, a^62, a^2 ]
43
Solved, But Available For Practice
Algorithm:  
Hardware:  
Runtime:  
Comments:  
Instance:   43
Solution file content:  
[ a^26, a^2, a^30 ]
[ 0, 1, a^10, a^8, a^4, a^11, a^2, a^27, a^9, a^22, a^26, a^24, a^29, a^5, a^3, a^15, a^25, a^18, a^20, a^19, a^7, a^13, a^28, a^21, a^14, a ]
41
Solved, But Available For Practice
Algorithm:  
Hardware:  
Runtime:  
Comments:  
Instance:   41
Solution file content:  
[ a^6, 1, a^5 ]
[ 0, a^16, a^25, a^28, a^9, a^7, a^12, a^2, a, a^27, a^24, a^6, a^13, a^26, a^22, a^19, a^8, a^14, a^20, a^4, a^5, a^11, a^17, a^30, a^18, a^10, a^3 ]
39
Solved, But Available For Practice
Algorithm:   Adaptation of the attack from the paper [CMT23] (available at https://eprint.iacr.org/2023/950) to a binary Goppa code with a square-free Goppa polynomial of degree 2. Sketch of the algorithm: (1) Construct the matrix code of quadratic relationships as defined in [CMT23] (2) Find 2 rank-2 matrices in the code corresponding to the same GRS code by solving the algebraic system related to the Pfaffian ideal specialized in 3 variables (= dimension of the associated variety) (3) Apply an adaptation of the attack from Section 6 of [CMT23] to recover a basis of the corresponding 2-dimensional GRS code (4) Apply a known attack on the GRS code to recover the secret support and multiplier (5) Find an automorphism for subfield subcodes of Cauchy codes to map the pair (support, multiplier) in an equivalent one that is a valid "Goppa representation", if necessary
Hardware:  
Runtime:   00:00:00:10
Comments:  
Instance:   39
Solution file content:  
[ a^26, a^29, a^12 ]
[ 0, a^25, a^22, a^13, a^16, a^7, a^30, a^28, a^29, a^26, a^8, a^18, a^14, a^23, a^21, a^3, a^4, a^12, a^10, a^5, a^6, a^11, a^15, a, a^24, a^19, a^20, a^27 ]
22
Solved, But Available For Practice
Algorithm:   Adaptation of the attack from the paper [CMT23] (available at https://eprint.iacr.org/2023/950) to a binary Goppa code with a square-free Goppa polynomial of degree 2. Sketch of the algorithm: (1) Construct the matrix code of quadratic relationships as defined in [CMT23] (2) Find 2 rank-2 matrices in the code corresponding to the same GRS code by solving the algebraic system related to the Pfaffian ideal specialized in 3 variables (= dimension of the associated variety) (3) Apply an adaptation of the attack from Section 6 of [CMT23] to recover a basis of the corresponding 2-dimensional GRS code (4) Apply a known attack on the GRS code to recover the secret support and multiplier (5) Find an automorphism for subfield subcodes of Cauchy codes to map the pair (support, multiplier) in an equivalent one that is a valid "Goppa representation", if necessary
Hardware:  
Runtime:   00:00:00:03
Comments:  
Instance:   22
Solution file content:  
[ a, a^16, a^21 ]
[ 0, 1, a^11, a^9, a^15, a^10, a^17, a^5, a^30, a^24, a^6, a^13, a^4, a^22, a^28, a^25, a^14, a^2, a^16, a^23, a^20, a^19, a^29, a^21, a^12, a^8, a^7, a^18, a, a^26, a^3, a^27 ]
Timeline
Updates23

Challenge Updates

Announcing the Winners of the TII McEliece Challenges

July 19, 2024, 8:16 a.m. PDT by Jamie Elliott

We are excited to announce the winners of the TII McEliece Challenges.

Please visit the recently published Meet the Winners page to see the winners.

Thank you to all who participated and followed!


Thank You for your Submissions

May 8, 2024, 2:01 p.m. PDT by Lulu

And just like that, it’s over! Thank you to all of you who sent in submissions. We can’t wait to finally see what you’ve been working so hard on. The HeroX and TII teams will be taking some time to review the Track 1A submissions and to confirm the results on the challenge leaderboard. Keep up the good work and an eye out for the final results!

Crowdsourcing would be nothing without the crowd — that’s you! Thank you for being an indispensable part of this process, and using your brainpower for the greater good.

Congratulations on completing your submission. This is not an easy process, and you deserve a pat on the back for your hard work and dedication. Thank you!


Eight Hours Left

May 8, 2024, 6 a.m. PDT by Lulu

You now have less than a day left to submit to the TII McEliece Challenges. Now’s the time to make final changes and send it off!

Please remember that the deadline is May 8, 2024 at 5:00pm Eastern Time. We don’t accept any late submissions, so do your best to get it in ahead of time.

We can’t wait to see what you’ve come up with! Best of luck.


Two Day Warning

May 6, 2024, 9 a.m. PDT by Lulu

The time has almost come! You now have two days left to finish your TII McEliece Challenges submissions. Your submissions are due on May 8, 2024 at 5:00pm Eastern Time.

We don’t accept any late submissions, so now is the time to make sure that everything is good to go. Double check file formats and make sure that all of your project components are easily accessible.

We are more than happy to answer your last-minute questions about the submission process. Post a question in the forum or leave a comment on this post, and we will be in touch with you.

We can’t wait to see the final projects. Good luck!


One Week Warning

May 1, 2024, 9 a.m. PDT by Lulu

This is your one week warning! The final submission deadline is May 8, 2024 at 5:00pm Eastern Time (New York/USA). No late submissions will be accepted, so make sure to give yourself plenty of buffer time.

If there’s anything you’re unsure about, there is still time to ask for help. Post on the discussion forum or leave a comment on this post. We’ll keep an eye out for your questions.

We can’t wait to see what you’ve been working on. Best of luck finishing up your submissions!


Forum1
Community
Press
FAQ
Meet the Winners