## Technology Innovation Institute

87,578  # 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 stage: Enter prize:$75,000
more
Summary
Timeline
Forum1
Community
Press
FAQ
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 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.

### 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.

Timeline

## Working from Home

Dec. 5, 2023, 9 a.m. PST by Lulu

If you’re used to working in an office environment, the process of working on a crowdsourced project can be daunting. Luckily we’ve been doing this for a while, and we’d like to share with you the tips that we’ve learned along the way.

Here are three tips to optimize your work from home experience:

1. Focus on results, not time spent working

In an office environment, we’re often led to think that we should be working eight hours a day, five days a week. In reality, not all of these hours are productive. When you’re able to control your own time at home, it’s a good idea to structure your day around specific tasks and goals.

2. Find the tools that work for you

If you’re working on your project with a team, you’ll need to find a way to connect with them remotely. Your team members may be from all around the world, and it’s important to figure out an effective communication strategy. Slack is a great tool for instant messaging, group chats, document sharing and reminders. For video calls, Zoom is a good go-to.

It’s easy to feel isolated while you’re working remotely. If you’re working with a team, it’s a good idea to schedule regular check-ins to connect with each other and boost morale. Zoom meetings don’t have to be all work, all the time. Take the time to connect with your team and find ways to support one another.

## Understanding the McEliece Cryptosystem

Nov. 30, 2023, 5 a.m. PST by Shane Jenkins In an era where digital information plays a pivotal role in our daily lives, securing data from prying eyes is of paramount importance. One of the cryptographic systems that has gained recognition for its potential to resist attacks from quantum computers is the McEliece Cryptosystem.

## Teamwork makes the Dream Work

Nov. 7, 2023, 9 a.m. PST by Lulu

Have you thought about forming a team to compete in the TII McEliece Challenges?

At this point in the challenge, it’s normal to start feeling a bit overwhelmed. Perhaps you’ve hit a roadblock, or you’re noticing the gaps in your own skillset. Forming a team is a great way to overcome these hurdles.

It will take time to form a team, so start reaching out to people now. You can connect with people in the forum, or you can browse the whole HeroX community by specialization at https://herox.com/crowdsourcing-community.

Why form a team?

1. Keep each other accountable

We all know that deadlines are tough, and it’s especially difficult to commit to a schedule by yourself. Creating checkpoints and milestones with your team members will help you keep each other on track.

2. Share skills

Everyone’s got a different set of skills. Have a great idea for a project, but need someone to help make it a reality? Got an innovative technical idea, but need help pulling it into an overall project? You need a team!

You can share expertise and specialized knowledge with your teammates. You’ll learn a ton, and your project will be all the better for it.

Why do all the work yourself? Divide and conquer the workload to save time and ease burnout. If you have an off week, your team can pick up the slack — and vice versa.

4. Make it fun

Your team will be by your side through all the highs and lows of the process, and they will make it all the more fun. This is also a great way to meet people with a shared set of interests. Just think, these may be your new best buds.

## Five of the Most Influential Projects in Cryptography

Oct. 25, 2023, 1:52 p.m. PDT by Jessie D'Amato Ford

Cryptography is a field that has seen numerous influential projects and developments over the years. Here are five historically significant projects and developments in cryptography. We hope these spur you to take a deeper look at cryptography’s dense history!

## Get Talking on the Forum

Oct. 24, 2023, 9 a.m. PDT by Lulu

Feeling stuck? Have questions, thoughts, or ideas about the challenge so far, and need a place to take them? That’s what the TII McEliece Challenges forum is for.

The forum is a great way to gain insights and generate ideas about different aspects of the challenge. Use the forum to ask questions, help out your fellow innovators, and maybe even make a few friends along the way.

You can browse through the forum to see what people have already been saying. To ask a question, click “New Topic” and write out your message.

HeroX checks the forum regularly, so it’s a good way to touch base with us directly.

See you on the forum!

Forum1
Community
Press
FAQ