Decoding Challenge Goppa-McEliece-1409

[Leo Ducas]

Dear all,

Does anyone has further information on the breaking of challenge 1409, from a month ago

https://decodingchallenge.org/goppa/record/27

by Shintaro Narisada, Hiroki Furue, Yusuke Aikawa, Kazuhide Fukushima, and Shinsaku Kiyomoto ? Apart from a claimed time of 30 hours (!), and the choice of an MMT variant algorithm, no further information on hardware is given, and I didn't find any report online.

For comparison, according to the decoding challenge website hints, it is supposedly about a 100 times harder than challenge 1284. This one took about 30 says on 512 cores if I am reading https://isd.mceliece.org/1347.html properly. 

Of course, it could just be that they had access to a million CPUs (512*24*100). Or maybe they have an MMT implementation on GPUs ?

Anyway, I am curious !
-- Léo

[Leo Ducas]

A million cores ! Not CPUs ;)

[D. J. Bernstein]

Leo Ducas writes:
> For comparison, according to the decoding challenge website hints, it is
> supposedly about a 100 times harder than challenge 1284.

Table 3 of https://cat.cr.yp.to/cryptattacktester-20231020.pdf reports
2^150.59 bit operations for isd2 (which includes MMT) for (3488,64) and
2^70.90 bit operations for isd2 for (1284,24), in both cases for code
rates in the usual 75-80% range.

That's about 80 extra bits for 40 extra errors, so you should estimate 2
extra errors as adding 4 bits. Or simply run CAT on whichever specific
size you're interested in.

> Or maybe they have an MMT implementation on GPUs ?

Yes, https://isd.mceliece.org/ points to a 2023.03.01 paper describing
an MMT implementation on GPUs.

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

[D. J. Bernstein]

I wrote:
> Or simply run CAT on whichever specific size you're interested in.

Specifically: I downloaded CAT, changed the problem list in
isdpredict1.py to say just 'N=1409,W=26', and ran

./isdpredict1.py > isdpredict1.out
./isdpredict2.py < isdpredict1.out > isdpredict2.out
./isdpredict-table.py < isdpredict2.out > isdpredict.tex

which took a total of 866 Zen 2 core-minutes. The results say 2^75.86
bit operations for isd2 for the 1409 challenge.

For comparison, CAT says 2^73.40 bit operations for isd2 for the 1347
challenge. To summarize, this 1409 record is 2.46 bits harder by isd2
than the 1347 record.

The 1347 record was set on CPUs simply running the PQCrypto 2008 attack
software. Out of curiosity, has anyone tried measuring the speed of the
best lattice-attack software from 2008?

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

P.S. The 2008 software used isd1; isd2 appeared a few years later. CAT
says 2^73.69 for isd1 for the 1347 challenge.

[Leo Ducas]

Thanks Dan,

>> Or maybe they have an MMT implementation on GPUs ?
> Yes, https://isd.mceliece.org/ points to a 2023.03.01 paper describing

> an MMT implementation on GPUs.

Wow, you are more efficient than google scholar ! I hadn't bruteforced the
right information subset of authors.

> To summarize, this 1409 record is 2.46 bits harder by isd2 than the 1347 record.

The decoding challenge website tooltip must be wrong then. I'll send a bug report.

Thanks for the correction !

The 1347 record was set on CPUs simply running the PQCrypto 2008 attack
software. Out of curiosity, has anyone tried measuring the speed of the
best lattice-attack software from 2008?

Oh, lattice software were nowhere then. I hadn't begin my PhD yet ;)

If my message suggested that there was recent software progress that should
threaten code-base cryptography, then I apologize, it was not my intent. My
stated assumptions did mention more hardware.

Best regards

-- Leo

[narisada shintaro]

Dear Prof. Léo Ducas, Prof. Daniel J. Bernstein, and all,
 
Thank you very much for your interest in our research.
We have implemented a variant of the MMT algorithm on a GPU
and used 10 desktop PCs equipped with 

a CPU (Intel Core i9-12900) and a GPU (GeForce RTX 3090 or RTX 4080) to solve Goppa-1409 challenge.

Our reference code is available in our paper:
https://www.jstage.jst.go.jp/article/transfun/advpub/0/advpub_2022CIP0023/_pdf
 
We had estimated the solving time to be 65 days on average with these 10 PCs, and
the probability of solving it within 30 hours is around two percent.
We will soon submit our paper on the results.
 
Best regards,
Shintaro Narisada

2023年12月4日月曜日 23:44:19 UTC+9 Leo Ducas:

[Brent Kimberley]

At the risk of embarrassing myself(*), I presume your MMT variant is more efficient and more stable than techniques which rely on Simulated Annealing / Markov-Chain Montecarlo – with noise injection?

 

* A long time ago… I wrote (relying on brute-force & ignorance) a couple special-purpose near-optimal inverse transforms for real time analogue and digital problems - up to 128b in size.

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of narisada shintaro
Sent: Tuesday, December 5, 2023 7:40 PM
To: pqc-forum <pqc-...@list.nist.gov>
Cc: Leo Ducas <leo.d...@gmail.com>; D. J. Bernstein <d...@cr.yp.to>; pqc-...@list.nist.gov <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Decoding Challenge Goppa-McEliece-1409

 

You don't often get email from nrs...@gmail.com. Learn why this is important

--
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/8c8da852-da7f-4924-9342-beb7deca8be2n%40list.nist.gov.

THIS MESSAGE IS FOR THE USE OF THE INTENDED RECIPIENT(S) ONLY AND MAY CONTAIN INFORMATION THAT IS PRIVILEGED, PROPRIETARY, CONFIDENTIAL, AND/OR EXEMPT FROM DISCLOSURE UNDER ANY RELEVANT PRIVACY LEGISLATION. No rights to any privilege have been waived. If you are not the intended recipient, you are hereby notified that any review, re-transmission, dissemination, distribution, copying, conversion to hard copy, taking of action in reliance on or other use of this communication is strictly prohibited. If you are not the intended recipient and have received this message in error, please notify me by return e-mail and delete or destroy all copies of this message.

[D. J. Bernstein]

narisada shintaro writes:
> 10 desktop PCs equipped with a CPU (Intel Core i9-12900) and a GPU
> (GeForce RTX 3090 or RTX 4080)

[ ... ]

> We had estimated the solving time to be 65 days on average with these
> 10 PCs

I think it's useful to translate this into cycles. The RTX 4080 has 9728
ALUs running between 2.210 GHz and 2.505 GHz, so 10 of those (total TDP:
3200 watts) carry out between 1.023 * 2^70 and 1.159 * 2^70 ALU cycles
in 65 days.

(If the cards last for 5 years then they use roughly $14000 in energy on
top of the $12000 purchase cost of the cards. Meanwhile they carry out
almost 2^75 ALU cycles, above 2^60 ALU cycles per dollar.)

An RTX 3090 has 10496 ALUs running between 1.395 GHz and 1.695 GHz, so
10 of those (TDP: 3500 watts) carry out between 0.697 * 2^70 and
0.846 * 2^70 ALU cycles in 65 days.

CAT gives a bigger number, 2^75.86, because the units are different: CAT
is counting bit operations (including the bit operations inside memory
access) rather than cycles. In principle one can figure out how many bit
operations a GPU is carrying out per ALU cycle in this computation.

For predicting what large-scale attackers can do per dollar or per watt,
it's better to look at ASICs than at GPUs: for example, an Antminer S17
(2520 watts) carries out roughly 2^86 bit operations in 65 days.

---D. J. Bernstein

[Brent Kimberley]

Antminer S17 (2520 watts) carries out roughly 2^86 bit operations in 65 days.

Those numbers are for a specific algorithm. 

In my opinion, the quoted maximums should be minimums -  for a small competitive efficient cogent utility.

---

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of D. J. Bernstein <d...@cr.yp.to>
Sent: Thursday, December 7, 2023 4:43:23 p.m.
To: pqc-...@list.nist.gov <pqc-...@list.nist.gov>

Subject: Re: [pqc-forum] Decoding Challenge Goppa-McEliece-1409

--
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/20231207214258.2117454.qmail%40cr.yp.to.

[narisada shintaro]

Dear Dr. Brent Kimberley and Prof. Daniel J. Bernstein, and all,
 
Thank you very much for your valuable comments and detailed analysis.
 
We are interested in the Simulated Annealing and Markov-Chain Monte Carlo algorithms you mentioned.
If you have a reference for the algorithm or implementation, we would appreciate it if you could share the information.
 
We would like to consider ASIC/FPGA implementations and conduct analyses using the cost-per-watt model in the future.
 
Best regards,
Shintaro Narisada

2023年12月8日金曜日 22:35:35 UTC+9 Brent Kimberley: