TII McEliece Challenges

[Andre]

Dear all,

prepare your laptops over the weekends as we are happy to announce the launch of TII McEliece challenges https://www.herox.com/TIIMcElieceChallenges.

The purpose of the TII McEliece Challenges is to enhance our understanding of the hardness of the problems that underpin the security of modern versions of the McEliece Cryptosystem, such as Classic McEliece. During the course of 1 year you can try to break McEliece keys and McEliece ciphertexts and win some money! Different to the already existing challenges at https://decodingchallenge.org/, ours include the tasks of McEliece key recovery, both practically and theoretically. And, there is a good bounty at stake. Participation can be done individually or in a team. You can keep track of the solved challenges in the Hall of Fame, as we are already used to from existing cryptanalytic challenges. The winners will be announced in June 2024. If you have more questions, please visit https://www.herox.com/TIIMcElieceChallenges/faq , or send us an email at mceliece....@tii.ae. Time to get your hands on efficient implementations and game changing ideas! Best regards,

Emanuele Bellini, Andre Esser and Elena Kirshanova

[D. J. Bernstein]

The key-recovery parameter sets in

https://github.com/ElenaKirshanova/tii_decoding_challenge/blob/main/key_rec_instances

generally have surprisingly small choices of t, and thus surprisingly
few choices of the Goppa polynomial g, so they're omitting one of the
central defenses in McEliece's original cryptosystem.

I'm also skeptical of the security estimates reported in the same file.
Reverse-engineering the numbers detects an underlying assumption that
support splitting for multiple support sets requires each possibility
for the support set to be handled separately---but the Classic McEliece
submission already questions exactly this assumption, saying "there
could be ways to merge work across possibilities". Concretely, it would
not be surprising for the algebraic techniques of

https://theses.hal.science/tel-01678829
https://eprint.iacr.org/2022/1715

to end up recovering keys more quickly than estimated in

https://github.com/ElenaKirshanova/tii_decoding_challenge/blob/main/key_rec_instances

for the parameter sets in that file.

It is, in any case, definitely not true that Classic McEliece relies on
this questionable assumption. On the contrary, Classic McEliece is
designed so that its QROM IND-CCA2 security relies purely on the OW-CPA
security of the original McEliece system; and the original McEliece
system has n=q, so there's only one possibility for the support set to
begin with. Section 4.1 of

https://classic.mceliece.org/mceliece-security-20221023.pdf

shows that the security of n<=q in Classic McEliece follows from the
security of n=q as in McEliece's original system, and gives examples of
calculating the (very small) tightness loss in the reduction.

To avoid confusion, I recommend changing the "McEliece key recovery" and
"Security Foundation" labels for this challenge, changing the
description of these parameter sets as merely being "reduced-size
instances", correcting the claim that this is a problem "on which the
security of McEliece is based", naming the source of the new security
estimates, acknowledging that the assumption underlying these estimates
was already questioned in the Classic McEliece submission, and citing at
least some representative examples of the extensive previous literature
on structural attacks.

---D. J. Bernstein (speaking for myself)

[Andre]

Dear Dan,

Thanks for your interest in the challenges.
The current state of the art on key recovery attacks on McEliece leaves a lot of room for discussions. This is exactly why we include those challenges: to advance the state of the art and reach a certain level of consensus.

We agree that our bit security estimates might not precisely capture the difficulty of these challenges. We did not initiated a detailed study, but rather needed a starting point for instance generation. Overall, this is not a problem, it simply means that the challenges might be easier or harder than stated. Determining the exact difficulty of those challenges would already be a nice outcome.

Also note that we are well aware of the fact that for the reduced-sized instances the algorithms found optimal might differ from those optimal for cryptographic instances, as it is stated in the "Challenges and Goals" section:

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

In track 1A of the challenges we ask for works that target the regime "on which the security of McEliece is based". However, in order to prevent any confusion or misinterpretation we added a corresponding entry in the FAQ (https://www.herox.com/TIIMcElieceChallenges/faq) that makes explicit that the impact from attack improvements on reduced-sized instances on cryptographic-sized McEliece instances has to be evaluated individually.

Best Regards,

Emanuele Bellini, Andre Esser and Elena Kirshanova

[D. J. Bernstein]

> We agree that our bit security estimates might not precisely capture
> the difficulty of these challenges.

My concern here is not with the level of precision. My concern is with
new strawman security estimates being incorrectly labeled as being part
of the security foundation of the McEliece system.

If these new estimates are (unsurprisingly) broken by the techniques
that I cited, then the "security foundation"/"McEliece"/... labeling
will make people believe, incorrectly, that the break is a problem for
the McEliece system. The labeling should be fixed.

The new FAQ entry exacerbates this problem by indicating, incorrectly,
that these challenges are simply the result of "down-scaling" normal
parameter selection to reach "approachable" sizes. This was already
suggested by the "reduced-size" terminology but is now more explicit.

As a concrete example, describing the challenge

{"n": 1008, "k": 898, "t": 11, "m": 10, "bitcomplexity": 252.052342314491}

as the result of "down-scaling" makes people think, incorrectly, that
this 2^252 is the result of scaling down security estimates that the
literature gives for cryptographic sizes.

Even if the "bitcomplexity" number is ignored, the "t" is surprisingly
small. One consequence is that the rate k/n = 898/1008 is very close to
the 92% cutoff for the https://eprint.iacr.org/2010/331 distinguisher.
It's well known that a feasible search will change the numbers a bit so
such cutoffs shouldn't be treated as sharp edges.

I'm not saying distinguishers necessarily turn into attacks. The point
is that this parameter set is not following normal parameter-selection
procedures. Normal parameter selection uses rates between 70% and 80%,
with much larger values of t than this challenge, many more choices for
the secret Goppa polynomial, and a much larger security margin against
key recovery.

For example, the smallest selected Classic McEliece parameter set has
(n,k,t) = (3488,2720,64), with rate 78%. The recommended 6688 and 6960
parameter sets have rates 75% and 78% respectively. The reasonably
scaled parameter set in https://decodingchallenge.org/goppa/record/26
has (n,k,t) = (1347,1072,25), with rate 80%.

[Andre]

Dear all,

We are excited to share some updates regarding the TII McEliece Challenges (https://www.herox.com/TIIMcElieceChallenges). 

Our challenge portfolio has now expanded to include new *prized* challenges in both key recovery and message recovery tracks. 

Notably, some of these challenges have been tailored to confidently align with the "Weekend on a Laptop" standard. Power up your laptops!

Our aim is to encourage participation from individuals who may not have access to extensive computing resources while also cultivating healthy competition on the leaderboard.

Stay tuned!

Best regards,
Emanuele Bellini, Andre Esser, and Elena Kirshanova

[Daniel Apon]

I always appreciate a good "laptop-weekends" metric for cryptanalysis =)
--Daniel

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/eebba492-65f4-4f9b-87a9-d5fdde673c7cn%40list.nist.gov.

[Simon Hoerder]

Sounds like a metric that’s almost ready to be submitted to the most authoritative of standardization bodies for pub’o’clock standards: https://www.theregister.com/Design/page/reg-standards-converter.html ;-)

Happy weekend,

Simon

On 29 Sep 2023, at 15:50, Daniel Apon <dapon....@gmail.com> wrote:



To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAPxHsSJGwH4tSMx_nUY6iufYf7FOMVBYhBK3O8FQRMAe7ud3bw%40mail.gmail.com.