The TII McEliece Challenges

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 prepare for this 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, 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 

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.

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 

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 70–74 and 80-90 bits of security.
 

Track 2A: Practical Message Recovery – 15.000$

This track consists of five different challenges with bit complexity 70, 71, 72, 73, and 74, respectively. The security levels are chosen such that current state-of-the-art algorithms (with slight tweaks) are able to solve these instances, if enough computational resources are available.

Track 2B: Practical Message Recovery – 40.000$

This track consists of eleven different challenges with a bit complexity of 80–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.

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 in range 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

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.

1. (1A) Best Theoretical Key Recovery Algorithms - $10,000
2. (1B) Best Practical Key Recovery Approach - $10,000
3. Message Recovery
   1. (2A) Best Practical Message Recovery of 70-74-bit Encryption - $15,000
   2. (2B) Best Practical Message Recovery of 80-94-bit Encryption - $40,000

Judging Criteria for Theoretical Key Recovery Algorithms (1A)

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