Subject: [CFRG] factoring integers by CVP and SVP algorithms

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 2 Mar 2021 15:47:20 -0800

Hi all,

I was linked to the paper https://eprint.iacr.org/2021/232.pdf with comment
"this destroys RSA".  I haven't attempted to evaluate that claim myself,
but figured that people here might be interested.

-Ben

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 3 Mar 2021 01:24:55 +0000

Benjamin Kaduk <[email-masked]> writes:

>"this destroys RSA".  I haven't attempted to evaluate that claim myself, but
>figured that people here might be interested.

The same thing cropped up on the cryptography list, my response there was:

  There's something odd about this, while the paper is by Claus Schnorr it's
  an old work from 2019, and the abstract on the IACR web page doesn't match
  the one in the paper.  In particular the paper never mentions RSA anywhere
  in it, compared to the abstract's "This destroyes [sic] the RSA
  cryptosystem".

Peter.

---

From: isis agora lovecruft <[email-masked]>
Date: Wed, 3 Mar 2021 01:41:50 +0000

>   in it, compared to the abstract's "This destroyes [sic] the RSA

There's pretty strong evidence that this was a hoax.

https://twitter.com/isislovecruft/status/1366922426106318851?s=20

-- 
 ♥Ⓐ isis agora lovecruft
_________________________________________________________
Pronouns: they/them
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://fyb.patternsinthevoid.net/isis.txt

---

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 2 Mar 2021 17:51:52 -0800

Thanks all for the quick sanity checks!

-Ben

On Wed, Mar 03, 2021 at 01:41:50AM +0000, isis agora lovecruft wrote:
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Tao Effect <[email-masked]>
Date: Tue, 2 Mar 2021 22:25:47 -0800

> On Mar 2, 2021, at 5:41 PM, isis agora lovecruft <[email-masked]> wrote:
> 

There doesn’t seem to be any evidence that this is a “hoax”.

Browsers should probably move to remove RSA.

Cheers,
Greg

---

From: Jeff Burdges <[email-masked]>
Date: Wed, 3 Mar 2021 11:39:48 +0100

Yes, almost surely Schnorr wrote this pdf file, but..  We’ve no idea who wrote the abstract or posted it on the eprint server.  lol

Schnorr has explored this technique rather publicly for many years, including circulating multiple versions of these research notes.   The version https://eprint.iacr.org/2021/232 is dated October 2019, but actually the most recent anyone pointed out is dated March 2020:
https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9.pdf

I’d expect this troll will achieve some good, by getting a few knowledgeable people to discuss the techniques with Schnorr.   :)  

> On 3 Mar 2021, at 07:25, Tao Effect <[email-masked]> wrote:

---

From: Watson Ladd <[email-masked]>
Date: Wed, 3 Mar 2021 07:25:06 -0800

> There doesn’t seem to be any evidence that this is a “hoax”.

The preprint is clearly incomplete and fragmentary, and a number of places
it's quite clear that things just don't work that way without more required
justification.

---

From: Thaddee Tyl <[email-masked]>
Date: Wed, 3 Mar 2021 19:36:04 +0100

> The preprint is clearly incomplete and fragmentary, and a number of places it's quite clear that things just don't work that way without more required justification.

Claus Schorr mistakenly uploaded the wrong file, an outdated draft.

He just uploaded the newest file:
https://eprint.iacr.org/eprint-bin/getfile.pl?entry=2021/232&version=20210303:182120&file=232.pdf

It will surely undergo extreme scrutiny, as it does claim:

> This destroys the RSA cryptosystem.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 3 Mar 2021 19:27:50 +0000

According to the formulas from the Section 3, factoring N ≈ 21024 in ≈ 298 arithmetic operations, and N ≈ 22048 in ≈ 2146 arithmetic operations.

I say that ePrint upload is a fake.

--

Regards,

Uri

There are two ways to design a system. One is to make is so simple there are obviously no deficiencies.

The other is to make it so complex there are no obvious deficiencies.

                                                                                                                                     -  C. A. R. Hoare

On 3/3/21, 13:37, "CFRG on behalf of Thaddee Tyl" <[email-masked] on behalf of [email-masked]> wrote:

    > The preprint is clearly incomplete and fragmentary, and a number of places it's quite clear that things just don't work that way without more required justification.

    > This destroys the RSA cryptosystem.

    CFRG mailing list

    [email-masked]

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 3 Mar 2021 19:36:36 +0000

Pardon me, but confirmed by who and to whom?

Did he tell just you that he’s still standing by his claim, and would he mind re-stating that statement on this list? 😉

--

Regards,

Uri

                                                                                                                                     -  C. A. R. Hoare

From: Georgio Nicolas <[email-masked]>
Reply-To: Georgio Nicolas <[email-masked]>
Date: Wednesday, March 3, 2021 at 14:34
To: Uri Blumenthal <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: Re: [CFRG] factoring integers by CVP and SVP algorithms

It was confirmed by multiple sources that Schnörr was indeed the author of the paper.

It also appeared that he had uploaded the wrong version of it, and is still standing by his claim.

https://twitter.com/leptan/status/1367103240228261894?s=21

-Georgio

On Wed, Mar 3, 2021 at 9:27 PM, Blumenthal, Uri - 0553 - MITLL <[email-masked]> wrote:

--

Regards,

Uri

                                                                                                                                     -  C. A. R. Hoare

    CFRG mailing list

    [email-masked]

---

From: isis agora lovecruft <[email-masked]>
Date: Wed, 3 Mar 2021 21:21:38 +0000

> I’d expect this troll will achieve some good, by getting a few knowledgeable people to discuss the techniques with Schnorr.   :)  

Sorry, I probably should have summarised the twitter speculations better.  But
yes, you're correct, yesterday this appeared to be an older version of a
legitimate paper Schnorr wrote in 2019, there's a newer version on his homepage,
and possibly someone else uploaded the older version to eprint, adding in the
HTML abstract "This destroyes [sic] the RSA cryptosystem."  (Please, can we have
"This destroyes _____" as a meme? lol)

Today, however, several colleagues spoke with Prof. Schnorr, who is asserting
that this technique with SVP and basis reduction "obviously destroys the RSA
cryptosystem."  A short while later Schnorr told the same colleagues that the
wrong version of the paper was uploaded.  A new version has just been uploaded
which repeats the claim (alas, without the beloved typo) in the paper itself
(and albeit still only in the abstract).

On the brighter side, I guess we all have a paper to read now. :)

Best regards,

---

From: Francois Grieu <[email-masked]>
Date: Thu, 4 Mar 2021 07:18:04 +0100

On 03/03/2021 at 22:21, isis agora lovecruft wrote :
> the wrong version of the paper was uploaded.  A new version has just been uploaded
> which repeats the claim

A preliminary analysis of that paper (PDF generated and posted 2021-03-03, see
at https://ia.cr/2021/232 ) shows an error that looks serious: the determinant
of the matrix on bottom of page 2 is underestimated. See the details in a
LaTex-friendly context at
https://crypto.stackexchange.com/a/88601/555

  François Grieu