$2050 that no quantum computer will break RSA2048 before 2050. Any takers?

2,443 views
Skip to first unread message

John Mattsson

unread,
Apr 18, 2023, 4:36:14 AM4/18/23
to pqc-...@list.nist.gov

Hi,

 

I bet $2050 that no quantum computer will break the RSA2048 factoring challenge before 2050. Any takers?

https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

 

Scientific wager is a noble artform practiced by e.g., Stephen Hawking and Richard Feynman.

https://en.wikipedia.org/wiki/Scientific_wager

 

It would be very good with an estimate from NIST/NSA when US government believe a Cryptanalytically Relevant Quantum Computer (CRQC) will actually be built. Australian Signals Directorate (ASD) believes currently stored encrypted data holdings will remain secure for however long the data remains sensitive [1]. I don't know Australian classification rules by heart but that seems to indicate 50-100 years. I know some countries have information where it can be up to 150 years before you can even request declassification. For US national security systems, a CRQC built 2070 would likely be problematic, but that timeline should not apply to industry unless necessary. Very little information in the private sector needs to be protected for very long times.

 

So far, the estimate from ASD seems to be the best public estimate. I have zero trust in statements form the quantum industry. As Professor Scott Aaronson (director of the University of Texas Quantum Information Center) accurately said:


“claims that we know how to get near-term speedups for optimization, machine learning, etc. are >95% BS!”[2]

 

Cheers,

John Preuß Mattsson

Expert Cryptographic Algorithms and Security Protocols

[1] https://www.itnews.com.au/news/asd-says-quantum-no-immediate-threat-to-encrypted-government-data-573483

 

[2] https://www.itnews.com.au/news/asd-says-quantum-no-immediate-threat-to-encrypted-government-data-573483

 

Markku-Juhani O. Saarinen

unread,
Apr 18, 2023, 5:27:50 AM4/18/23
to pqc-forum, John Mattsson
On Tuesday, April 18, 2023 at 9:36:14 AM UTC+1 John Mattsson wrote:

I bet $2050 that no quantum computer will break the RSA2048 factoring challenge before 2050. Any takers?

(..)

It would be very good with an estimate from NIST/NSA when US government believe a Cryptanalytically Relevant Quantum Computer (CRQC) will actually be built. Australian Signals Directorate (ASD) believes currently stored encrypted data holdings will remain secure for however long the data remains sensitive [1]. I don't know Australian classification rules by heart but that seems to indicate 50-100 years. I know some countries have information where it can be up to 150 years before you can even request declassification. For US national security systems, a CRQC built 2070 would likely be problematic, but that timeline should not apply to industry unless necessary. Very little information in the private sector needs to be protected for very long times.


Hi John,

I can't speak for ASD, but I guess someone there might take your bet. The current Australian ISM actually states that RSA-2048 is considered secure only until 2030 (7 more years, not 150):

ASD has published post-quantum guidance largely in line with NSA and GCHQ/NCSC assessments. They suggest trials/piloting until the actual NIST PQC standards are out. See https://www.cyber.gov.au/resources-business-and-government/governance-and-user-education/governance/planning-post-quantum-cryptography

Recall that the ongoing U.S. Post-Quantum Transition within defense and government sectors (National Security Memorandums NSM-08, NSM-10, elements of DoD Crypto Modernization 2, etc.) is actually driven by threat assessments by NSA. It is not a secret that the July 2015 assessment by NSA / Committee of National Security Systems ( CNSSAM 02-15 ) largely initiated the NIST Post-Quantum Cryptography standardization process too.

Cheers,
- markku

John Mattsson

unread,
Apr 18, 2023, 7:08:37 AM4/18/23
to Markku-Juhani O. Saarinen, pqc-forum

>

RSA-2048 is considered secure only until 2030

RSA-2048 should already have been phased out for most use cases. Because of classical computers, _not_ because of quantum computers. NIST and ANSSI only allows RSA-2048 (and FFDH2048) if the protected asset does not have to be protected after 2030. BSI states that RSA-2048 (and FFDH2048) can be used up until the year 2022.

 

It would be much more interesting with government guidelines for RSA-4096. The CNSA 2.0 timelines makes total sense for NSS use cases that need to protect TOP SECRET information for a century. But unless NSA is doing this transition many many decades too late, the same timelines should likely not apply to other use cases that do not need to protect TOP SECRET information for a century….

Cheers,
John

--
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/0e3fded5-e3af-43e4-829b-6856485602d5n%40list.nist.gov.

Thom Wiggers

unread,
Apr 18, 2023, 7:31:18 AM4/18/23
to John Mattsson, Markku-Juhani O. Saarinen, pqc-forum
I'd like to refer to this prior art https://mobile.twitter.com/frhenr/status/923330560335937536 ;-)

Op di 18 apr 2023 om 13:08 schreef 'John Mattsson' via pqc-forum <pqc-...@list.nist.gov>:

Brent Kimberley

unread,
Apr 18, 2023, 8:27:50 AM4/18/23
to John Mattsson, Markku-Juhani O. Saarinen, pqc-forum

If you like charts and tables, RSA-2048 appears to provide up to “security strength” of “112-bits”.

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.

John Mattsson

unread,
Apr 18, 2023, 8:58:00 AM4/18/23
to pqc-forum, Markku-Juhani O. Saarinen, Thom Wiggers

I think NIST SP 800-57 Part 1 is an excellent document. It specifies in detail how to work with algorithm lifetimes and how to transition between algorithms with different strengths, i.e., exactly what we need for the PQC migration. An essential idea in NIST SP 800-57 is the security life of the data the algorithm is protecting. This makes very much sense and means that a use case requiring 50 years protection needs to migrate to a stronger algorithm 40 years before a use case that only requires 10 years of protection.

 

Suggestions that all use cases need to migrate to PQC at the same time makes no sense at all and go completely against NIST SP 800-57. I really hope NIST will keep the excellent SP 800-57 Part 1 also for the PQC migration.

 

https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r5.pdf


Chart, diagram, box and whisker chart

Description automatically generated with medium confidence

D. J. Bernstein

unread,
Apr 18, 2023, 9:46:19 AM4/18/23
to pqc-...@list.nist.gov
'John Mattsson' via pqc-forum writes:
> I bet $2050 that no quantum computer will break the RSA2048 factoring
> challenge before 2050. Any takers?

Happy to take you up on that. I expect the factorization of RSA-2048 to
be publicly announced, with the factors, and plausibly claimed to be
done by quantum computing, long before 2050. (I'm already on record
betting on 2032; see https://blog.cr.yp.to/20220129-plagiarism.html.)

A quantum circuit running a Shor-type algorithm needs enough physical
qubits, a low enough per-qubit error rate, enough error correction to
build logical qubits, and a quantum modular-exponentiation algorithm;
so it's good to watch reported advances in each of these four areas.
Advances in the number of qubits and the error rate are plotted in

https://sam-jaques.appspot.com/quantum_landscape_2022

but beware that the graph incorrectly portrays error correction and
exponentiation algorithms as unchanging when in fact they've been
improving---and presumably will continue to do so, for example with
faster multiplication algorithms and with techniques to encode multiple
logical qubits more efficiently than encoding each qubit separately.

> So far, the estimate from ASD seems to be the best public estimate. I
> have zero trust in statements form the quantum industry.

Google, IBM, etc. certainly have an incentive to hype the advances, but
insisting on quantification and on scientific papers makes it hard for
them to make the overall progress sound more rapid than it actually is.
If you're looking for a survey of expert risk assessments rather than
extrapolating the numbers yourself, you can find a 67-page report

https://globalriskinstitute.org/publication/2022-quantum-threat-timeline-report/

that documents its methodology, _quantifies_ the risk assessments, and
includes systematic comparisons to previous risk assessments.

Meanwhile, if you're looking at incentives, you have to consider the
fact that large-scale attackers are recording RSA/ECC ciphertexts today,
are working on building quantum computers, and have a strong incentive
to convince people to delay post-quantum rollout as long as they can.

When ASD says it "does not expect it will possible within these lengths
of time to build a quantum computer that can break the algorithms and
key sizes described in the ISM", do we have a clear statement of what
"these lengths of time" are? Is ASD saying what the basis for its
(claimed) expectation is? Are the details provided for public review,
giving an opportunity for errors to be discovered and corrected?

When NSA's FAQ poses the question "Isn't quantum computing a long way
off?" and answers it by talking only about "systems that will be used
many decades in the future" and not about _attackers recording data
right now_, here are two different hypotheses to consider:

* This is NSA honestly believing, for reasons so obvious that they
don't require any explanation or references, that the probability
of attackers having quantum computers in time to exploit any of
today's data is so close to 0 as to not even be worth mentioning.

* This is NSA trying to mislead the public, as a tiny part of its
quarter-billion-dollar-per-year program to "covertly influence
and/or overtly leverage" cryptography to make it "exploitable".

Some user data needs long-term confidentiality. This is even a legal
right (depending on the country) for, e.g., patients talking to doctors,
clients talking to lawyers, whistleblowers talking to journalists, etc.
From a risk-management perspective, we have to assume that quantum
computers are built within the timeframe where today's data still has to
be kept confidential. This means that we already have a security
disaster today. Every day that we fail to act is giving away more user
data to attackers.

> For US national security systems, a CRQC built 2070 would likely be
> problematic, but that timeline should not apply to industry unless
> necessary. Very little information in the private sector needs to be
> protected for very long times.

The U.S. government intercepted private activities of Martin Luther
King, Jr., in the 1960s, used those intercepts for extortion, and is
continuing to seal the records---through 2027, last I heard. That's a
longer timeframe than you're talking about. I doubt that the family
thinks it'll be okay to release the intercepts in 2027.

I expect that Hoover-style attackers recording information in 2023 will
find considerable volumes that remain useful for extortion in 2070, and,
more to the point, in the much shorter timeframe when I expect the
attackers to have large quantum computers.

> As Professor Scott Aaronson (director of the University of Texas
> Quantum Information Center) accurately said:
> “claims that we know how to get near-term speedups for optimization,
> machine learning, etc. are >95% BS!”

My understanding is that he's criticizing exaggeration of (1) the range
of algorithms with known quantum speedups and (2) the practical value of
baby quantum computers that are too noisy to support logical qubits.

---D. J. Bernstein
signature.asc

Lie Breakers

unread,
Apr 18, 2023, 11:59:21 AM4/18/23
to pqc-forum, D. J. Bernstein, pqc-...@list.nist.gov
This is a good idea! Especially in the PQC field, people always like novelty, and that includes some interesting bets. However, there is a suspicion of hype surrounding these bets. For example, there is a foundation called ABCMint, whose chairman Jin Liu, who is likely Chinese, once publicly offered a $40 bet to break a PQC digital signature called "Rainbow Signature" invented by Professor Jin Tai Ding, claiming that no one would be able to break it within 100 years. However, earlier this year, Rainbow was broken by Ward Beullens of IBM's research team, and the break was confirmed by Professor Ding, but there has been no news of Jin Liu fulfilling his $400,000 promise.

Such hype and exaggeration are not uncommon in various media, with many companies and individuals making grand claims about their project's abilities without providing specific evidence or data to support their claims. This can make it difficult for outsiders to distinguish genuine breakthroughs from mere hype.

At the same time, there is no denying the excitement and potential of PQC. As quantum computers continue to improve, they may eventually be able to break many of the encryption schemes that currently protect our data, from online banking to national security communications. This means that a race to develop and deploy new PQC algorithms that can provide security in a post-quantum world is underway.

In this context, scientific wagers like the one you proposed can be a useful way to encourage researchers and companies to focus on developing practical, secure PQC algorithms rather than simply chasing hype or making grand claims. However, it is important to ensure that such wagers are based on realistic timelines and assessments of the current state of the field, rather than wishful thinking or hype.

Lie Breakers

unread,
Apr 18, 2023, 12:20:08 PM4/18/23
to pqc-forum, Lie Breakers, D. J. Bernstein, pqc-...@list.nist.gov
Correct my information, it's $400,000 instead of $40

John Sahhar

unread,
Apr 18, 2023, 2:46:02 PM4/18/23
to John Mattsson, pqc-...@list.nist.gov
Hello John,

Wager accepted.

Furthermore, I wager anyone 1,000,000$ USD that solving the discrete logarithm of any 256 bit Elliptic Curve will be computationally feasible by a quantum computer before or during the year 2050.

Any takers?

--
Regards,
John Sahhar
Cryptographer @ Entropy Cryptography Services, Inc. 



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

Daniel Apon

unread,
Apr 18, 2023, 5:44:36 PM4/18/23
to John Sahhar, John Mattsson, pqc-...@list.nist.gov
Hello John Mattson,

Along with Dan Bernstein and John Sahhar, I’d accept your $2050 bet “that no quantum computer will break the RSA2048 factoring challenge before 2050.”

Please let me know if your offer is inflation-adjusted or an absolute dollar value. (In the later case, I’ll happily enjoy the year-2050 cheeseburger you’re offering to buy me for my retirement party!)

Please ACK to this thread if you are accepting these three “takers” of your bet. I’m happy to figure out how to get binding legal documents drafted, signed, and executed!

Cheers,
—Daniel
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+unsubscribe@list.nist.gov.

--
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+unsubscribe@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CALuYY16XNkadiGkKJSi1ZxOUmn4F_p0aOzrmj25%3DQCYp13FBzw%40mail.gmail.com.

Daniel Apon

unread,
Apr 18, 2023, 6:11:04 PM4/18/23
to pqc-forum, Daniel Apon, John Mattsson, pqc-...@list.nist.gov, John Sahhar
P.S. John Mattsson, if you are serious, then I propose we put these funds in escrow now, allow them to grow with inflation of the U.S. Dollar, and I will designate (in the event that a quantum computer breaks the RSA2048 factoring challenge before 2050) that my pay-out is sent in full to the U.S. National Science Foundation as a donation.

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

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

Tony Arcieri

unread,
Apr 18, 2023, 6:18:05 PM4/18/23
to John Mattsson, pqc-...@list.nist.gov
I've thought about making various bets about post-quantum cryptography like this, but I would suggest the proceeds to go charity

Matthew Sparkes

unread,
Apr 19, 2023, 6:03:36 AM4/19/23
to Tony Arcieri, John Mattsson, pqc-...@list.nist.gov
Would those making or accepting bets be available for a chat? I cover quantum computing and cryptography for New Scientist magazine and would love to pick your brains.

On Tue, Apr 18, 2023 at 11:18 PM Tony Arcieri <bas...@gmail.com> wrote:
I've thought about making various bets about post-quantum cryptography like this, but I would suggest the proceeds to go charity

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


--
Tel: 07974 918855
Twitter: twitter.com/Sparkes

John Mattsson

unread,
Apr 19, 2023, 6:15:45 AM4/19/23
to D. J. Bernstein, pqc-...@list.nist.gov

D. J. Bernstein wrote:

 

>'John Mattsson' via pqc-forum writes:

>> I bet $2050 that no quantum computer will break the RSA2048 factoring

>> challenge before 2050. Any takers?

> 

>Happy to take you up on that. I expect the factorization of RSA-2048 to

>be publicly announced, with the factors, and plausibly claimed to be

>done by quantum computing, long before 2050. (I'm already on record

>betting on 2032; see https://protect2.fireeye.com/v1/url?k=31323334-501cfaf3-313273af-454445554331->4c7020056d99329c&q=1&e=fba41b67-a7a8-47fb-8120-9a289442823d&u=https%3A%2F%2Fblog.cr.yp.to%2F20220129->plagiarism.html.)

 

Great, then it's on like Donkey Kong!

Wow, I didn't know you had so many ongoing bets. I agree that you will win your JPEG bet, that will probably be true in 2050 as well. I think your second bet will be a draw, and I do of course think you will lose your third bet ;)

 

>A quantum circuit running a Shor-type algorithm needs enough physical

>qubits, a low enough per-qubit error rate, enough error correction to

>build logical qubits, and a quantum modular-exponentiation algorithm;

>so it's good to watch reported advances in each of these four areas.

>Advances in the number of qubits and the error rate are plotted in

> 

> 

>but beware that the graph incorrectly portrays error correction and

>exponentiation algorithms as unchanging when in fact they've been

>improving---and presumably will continue to do so, for example with

>faster multiplication algorithms and with techniques to encode multiple

>logical qubits more efficiently than encoding each qubit separately.

 

Yes, Samuel Jaques website is indeed a great resource and algorithms have definitely improved.

 

I do however not think that the physical aspects of quantum computers will continue to improve as fast as they have in the past years. Any near-term applications for quantum computers are highly uncertain. As stated in National Academies consensus study report "Quantum Computing Progress and Prospects"

 

"a “noisy intermediate-scale quantum computer,” or NISQ computer, probably isn’t going to be of much practical use. “There are at present no known algorithms/applications that could make effective use of this class of machine,” says the committee. That might change. Or it might not. And if it doesn’t, it seems unlikely that industry will keep investing in quantum computing long enough for the technology to pay dividends.”

 

https://nap.nationalacademies.org/catalog/25196/quantum-computing-progress-and-prospects#toc

 

In the current ecomony, money is not free anymore and investors are increasingly reluctant to fund activities making losses. I think we will see a very drastical reduction in the quantum computing industry. The only thing stopping that would be if they find practical use cases soon and start making money, my estimate is that they will not.

 

The quantum computing industry is fundamentally different form the classical computing industry when it started. For classical computing there was many profitable use cases from the start and always very strong demand for more and more transistors. The quantum computing industry has currently no practical use cases and it is unclear when there will be practical money making use cases.

 

The quantum industry is suffering from what Google’s former head of quantum computing hardware John Martini called "quantity hype". The end station of quantity hype is death of the quantum computing industry illustrated with a skull in the linked article.

https://www.enterpriseai.news/2018/04/27/quantum-error-correction-googles-strategy-for-qubit-accuracy/


>> So far, the estimate from ASD seems to be the best public estimate. I

>> have zero trust in statements form the quantum industry.

> 

>Google, IBM, etc. certainly have an incentive to hype the advances, but

>insisting on quantification and on scientific papers makes it hard for

>them to make the overall progress sound more rapid than it actually is.

>If you're looking for a survey of expert risk assessments rather than

>extrapolating the numbers yourself, you can find a 67-page report

> 

> 

>that documents its methodology, _quantifies_ the risk assessments, and

>includes systematic comparisons to previous risk assessments.


I am not as fond of the "2022 Quantum Threat Timeline Report" as you seem to be. Much of the report is based on a survey among researchers and companies working on quantum computers. I don't think that is a good way to do a risk assesment at all. The sample risks being very biased and people are often way too optimistic about their own work. If you asked fusion researchers in 1930, they also said working fusion reactors were very likely in the next 20 years. The probabilities in the report does not align with what I have heard from quantum researchers in other fields of quantum research not building quantum researchers themselves. One professor told me he thought CRQCs would never be built, or at least not in the next 100 years

 

Given that the survey is likely sampled from the same set of people that are responsible for the >95% BS claims about near-term speedups, a reasonable assumtion would be that the time and probability estimates might also be >95% BS.

 

I think the National Academies consensus study report "Quantum Computing Progress and Prospects" from 2019 seems much better. It concludes that the emergence of a CRQC during the next decade would be highly unexpected.

 

https://nap.nationalacademies.org/catalog/25196/quantum-computing-progress-and-prospects#toc

 

>Meanwhile, if you're looking at incentives, you have to consider the

>fact that large-scale attackers are recording RSA/ECC ciphertexts today,

>are working on building quantum computers, and have a strong incentive

>to convince people to delay post-quantum rollout as long as they can.

> 

>When ASD says it "does not expect it will possible within these lengths

>of time to build a quantum computer that can break the algorithms and

>key sizes described in the ISM", do we have a clear statement of what

>"these lengths of time" are? Is ASD saying what the basis for its

>(claimed) expectation is? Are the details provided for public review,

>giving an opportunity for errors to be discovered and corrected?


No, given that ASD is Australias Signals Intelligence Agency the public information is as usual minimal. Not sure about how long documents can be classified in Australia, but in the US and many other countries there is no firm end date, but in the US you do need special permission to classify longer than 75 years.

https://www.govinfo.gov/content/pkg/WCPD-1995-04-24/pdf/WCPD-1995-04-24-Pg634.pdf

>When NSA's FAQ poses the question "Isn't quantum computing a long way

>off?" and answers it by talking only about "systems that will be used

>many decades in the future" and not about _attackers recording data

>right now_, here are two different hypotheses to consider:

> 

>   * This is NSA honestly believing, for reasons so obvious that they

>     don't require any explanation or references, that the probability

>     of attackers having quantum computers in time to exploit any of

>     today's data is so close to 0 as to not even be worth mentioning.

> 

>   * This is NSA trying to mislead the public, as a tiny part of its

>     quarter-billion-dollar-per-year program to "covertly influence

>     and/or overtly leverage" cryptography to make it "exploitable".


I don't think that is an exhaustive list. I absolutely think NSA believe there is a risk that a CRQC is build in time frames to exploit todays data. I wish NSA would share more of their estimates here, but NSA does not really like to share information unless they find it necesary. The risk does not at all have to be close to 0. An estimated 25% risk that a CRQC is built in 50 years would likely make NSA act as they do right now. Forcing NSS systems to move to PQC as soon as possible.

 

I have not seen any signs that NSA is trying to mislead, but NSA definitly has an interest in influencing the industry to tag along quickly in the PQC migration to get cheap off-the-shelf PQC products for NSS.

 

>Some user data needs long-term confidentiality. This is even a legal

>right (depending on the country) for, e.g., patients talking to doctors,

>clients talking to lawyers, whistleblowers talking to journalists, etc.

>From a risk-management perspective, we have to assume that quantum

>computers are built within the timeframe where today's data still has to

>be kept confidential. This means that we already have a security

>disaster today. Every day that we fail to act is giving away more user

>data to attackers.

> 

>> For US national security systems, a CRQC built 2070 would likely be

>> problematic, but that timeline should not apply to industry unless

>> necessary. Very little information in the private sector needs to be

>> protected for very long times.

> 

>The U.S. government intercepted private activities of Martin Luther

>King, Jr., in the 1960s, used those intercepts for extortion, and is

>continuing to seal the records---through 2027, last I heard. That's a

>longer timeframe than you're talking about. I doubt that the family

>thinks it'll be okay to release the intercepts in 2027.

> 

>I expect that Hoover-style attackers recording information in 2023 will

>find considerable volumes that remain useful for extortion in 2070, and,

>more to the point, in the much shorter timeframe when I expect the

>attackers to have large quantum computers.

 

Yes, there are definitely personal information that require very long confidentiality as well, but most information don’t. I hope NIST will continue to long-term in advance announce end years for when data can be actively protected with certain algorithms. This allows people to continue to use NIST SP 800-57 Part 1 to determine how long certain algorithms can be used for their use cases based on their need for long-time confidentiality.

 

Note that NIST announcing e.g., that P-P384 can only be used as key exchange for data that do not need to be confidential longer that 2050 would have very drastic implications. That would imply that NIST believe huge amount of US TOP SECRET information protected using the CNSA 1.0 suite would be readable by other hostile national states by that time. Much of that information would still be classified. It would mean that NIST thinks NSA failed to see the risk in time and updated CNSA way too late.

 

>> As Professor Scott Aaronson (director of the University of Texas

>> Quantum Information Center) accurately said:

>> “claims that we know how to get near-term speedups for optimization,

>> machine learning, etc. are >95% BS!”

> 

>My understanding is that he's criticizing exaggeration of (1) the range

>of algorithms with known quantum speedups and (2) the practical value of

>baby quantum computers that are too noisy to support logical qubits.

> 

>---D. J. Bernstein

 

Cheers,

John

 

Michele Mosca

unread,
Apr 19, 2023, 3:51:11 PM4/19/23
to John Mattsson, pqc-...@list.nist.gov

Hello John,

I'll take your 1:1 bet.   

This is a bet of the following form, with a year Z and risk threshold 1/(M+1), for Z=2050 and M=1:

"I bet $M against $1 that no quantum computer will break the RSA2048 factoring challenge before year Z" .

This is particularly interesting for M where greater than 1/(M+1) chance of not being ready in time is considered too risky (M thus depends on what is at stake and one's corresponding risk tolerance).

e.g. M=19 corresponds to 5% risk.  M=3 corresponds to 25% risk.

Do you have a Z for M=19?

Best regards,
Michele


From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Daniel Apon <dapon....@gmail.com>
Sent: April 18, 2023 5:44 PM
To: John Sahhar <jo...@entropy.xyz>
Cc: John Mattsson <john.m...@ericsson.com>; pqc-...@list.nist.gov <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] $2050 that no quantum computer will break RSA2048 before 2050. Any takers?
 
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/CAPxHsSJL2roFgGJFCOHDQV-opoDHWTO0mdeAq%3DAuqQvbZ_eaqw%40mail.gmail.com.

Dan Brown

unread,
Apr 19, 2023, 4:39:34 PM4/19/23
to pqc-forum, John Mattsson
What about ECC, such as one of the unsolved Certicom ECC Challenges, maybe 131 bits?

Side point: PQC will soon be deployed. Post-PQC, public researchers have less incentive to break ECC/RSA.

John Mattsson

unread,
May 3, 2023, 9:21:43 AM5/3/23
to pqc-...@list.nist.gov, D. J. Bernstein, John Sahhar, Daniel Apon, Michele Mosca

Hi,

 

If I counted correctly, Daniel J. Bernstein, John Sahhar, Daniel Apon, and Michele Mosca accepted my bet. I am accepting the four "takers" and close the bet for more takers. I would be happy to let the money go to charity such the U.S. National Science Foundation. Also fine to formalize the bet by signing a contract if anybody wants that, maybe that could be arranged at some NIST workshop.

 

The bet is already mentioned on Wikipedia and got a whole article in New Scientist.

 

https://en.wikipedia.org/wiki/Scientific_wager

 

https://www.newscientist.com/article/2370022-cryptographers-bet-cash-on-when-quantum-computers-will-beat-encryption/

 

Seems like quite a lot of people are fed up with the quantum hype. At the recent RSA conference Adi Shamir said:

 

“If I’m trying to characterize what has been delivered in practice in quantum computing. I must say that the main thing which has been delivered is more promises”

 

"it won’t be for another 30 or 40 years until they are able to pose a risk."


https://www.sdxcentral.com/articles/analysis/rsa-cryptographers-panel-debate-quantum-computing-snowden-blockchain-and-ai/2023/04/

 

And in the New Scientist article Paul Hoffman says:

 

"quantum computers will crack encryption in 2060 “at the very earliest”, and that it is entirely possible that the moment will never come."

 

The two main reasons I expect a << 50% chance that quantum computers will break RSA-2048 before 2050 are:

 

- Unless there are drastic improvements in algorithms, quantum computers need 6 orders of magnitude more qubits while keeping or slightly improving the error rate. I don't see that happening before 2050. The technical difficulties are enormous, and I don’t believe there will be funding.

 

- It does not seem like security agencies around the world believe in CRQCs before 2050, if they were they would panic a lot more. The existence of a CRQC before 2050 would mean that most security agencies have failed to protect their nations classified information. The exception would be Sweden that never trusted public key crypto (too much structure) and continued to rely solely on symmetric crypto :) NSA expects the transition to QR algorithms for NSS to be complete by 2035, and earlier transitions like Suite B took significantly longer time than expected.

 

Given that US NSS is planning to migrate in the next 12 years, most other use cases can wait several more decades following the standard for algorithm migration, NIST SP 800-57. DNSSEC has already decided that they will not transition to PQC now, which makes a lot of sense to me.

 

Cheers,

John

Paul Hoffman

unread,
May 3, 2023, 10:09:12 AM5/3/23
to John Mattsson, pqc-...@list.nist.gov
On May 3, 2023, at 6:21 AM, 'John Mattsson' via pqc-forum <pqc-...@list.nist.gov> wrote:
> And in the New Scientist article Paul Hoffman says:
> "quantum computers will crack encryption in 2060 “at the very earliest”, and that it is entirely possible that the moment will never come."

Of course, that quote misses the context I gave the author. The exact thing I sent to the author was:

=====
2060 at the very earliest, but with two important distinctions:

- I have absolutely no track record for making predictions like this, so asking me might get an interesting result, but not a useful one. (Quite frankly, no one else seems to have any track record at predicting, but that doesn't stop them from making predictions when you ask them.)

- "Never" is a real possibility unless there are some significant engineering improvements. I think such improvements are much more likely if there are real non-cryptographic uses for quantum computers (where "real" means computing things that are not exclusively about the quantum world). If those non-cryptographic uses don't materialize, then I think "never" is quite likely (except possibly three or four such computers, each owned by a military).
=====

--Paul Hoffman

Tony Arcieri

unread,
May 3, 2023, 3:28:28 PM5/3/23
to John Mattsson, pqc-...@list.nist.gov
On Tue, Apr 18, 2023 at 2:36 AM 'John Mattsson' via pqc-forum <pqc-...@list.nist.gov> wrote:

I bet $2050 that no quantum computer will break the RSA2048 factoring challenge before 2050.


I'd potentially be interested in a shorter-term bet for charity with a smaller semiprime size.

How about the original RSA100 challenge? But with the caveat that a generalized implementation of Shor's algorithm must be used, as opposed to one where the quantum circuit is specialized for the known prime factors in advance.

Though the interesting question there is: how soon do others expect that to happen?

--
Tony Arcieri

Thomas Braun

unread,
May 5, 2023, 9:19:46 AM5/5/23
to pqc-forum, Tony Arcieri, pqc-...@list.nist.gov, John Mattsson
Let's be real. How do we determine what information source constitutes as "true" or "valid". Who has the "authority" to tell us when quantum computers supposedly break RSA2048? I ask this because, clearly, there is information asymmetry between public-sector knowledge and hidden-sector knowledge (AKA special access programs, or unacknowledged special access programs). As 60 minutes shows, there is technology light years ahead of the public sector right in plain sight. RSA 2048 may already be broken, and we may already be in a post-quantum world. https://www.cbsnews.com/news/ufo-military-intelligence-60-minutes-2021-08-29/

Daniel Apon

unread,
May 5, 2023, 1:27:12 PM5/5/23
to Thomas Braun, pqc-forum, Tony Arcieri, John Mattsson
Whether there is a private break of RSA-2048 is outside the scope of a public scientific wager..

It's simple to post an RSA challenge in public (there are already many). Across many such challenges from disparate parties, presumably not one party knows the solution a-priori for all challenges.

Those claiming RSA-2048 will be broken in public by 2050 should be claiming (as I am) that it will be "obvious and common knowledge in public" by 2050.
(This naturally includes, on those making bets that a break will happen, that there will be other side-events that incentivize at least one party with a large-scale quantum computer to demonstrate this in public by 2050.)

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

Michele Mosca

unread,
May 7, 2023, 4:45:28 PM5/7/23
to Tony Arcieri, pqc-...@list.nist.gov

Hello Tony,  

  

I like the idea of betting on a meaningful shorter-term milestone.  

  

1)  

Some comments on your suggestion:  

  

i)  

Since Shor's algorithm runs in slightly more than quadratic time, without a significant advance in quantum factoring algorithms, we should expect a bit more than 40x more resources (very roughly) to go from factoring 330 bit semi-primes to 2048 bit semi-primes.   E.g. >5x memory and >8x time.

So the difference is a bit more than 5 bits of security.

That's a lot smaller than the gap between the best classical algorithms for RSA100 and for RSA110, or between RSA300 and 2048 bit RSA. 

 

ii)  

Implementing Shor's algorithm for RSA100 based on what we know today requires fault-tolerant logical qubits (see https://arxiv.org/abs/1902.01448 for an assessment of some alternative approaches that have been proposed, and why we don't think they represent meaningful cryptanalysis benchmarks).    

Most likely (in my opinion), to achieve factoring RSA100 with a quantum computer, the major advances/breakthroughs needed to break 2048-bit RSA with a quantum computer will have been achieved.  So RSA100 is not a good mid-way point.    

[I might be wrong, of course.... maybe eventually available technology and fault-tolerant error correction will allow us to cram just enough logical qubits on available chips and in available cryostats to break RSA100, but will require significant advances (e.g. entangling across different chips, or significant miniaturization) to break 2048-bit RSA.]  

  

iii)  

Checking for no cheating will be non-trivial.    If one produces the factors of a 2048-bit RSA challenge, we'll be pretty confident they didn't do it classically and then used the quantum computer to pretend to factor it and just output the (already known) answer.  i.e. there are fewer reasons to need to test or validate the implementation.

  

But factoring 100 digit numbers is easy to do classically, so one would have to be an expert on quantum computing, and have intimate access to the code and hardware to be able to check if the quantum computer actually did the factorization versus just ran a noisy instance of Shor's algorithm and then rigged the computer to output a string that when post-processed leads to a factorization.  

  

2)  

In our threat timeline survey, we asked experts for what would be a good "Next experimental milestone to demonstrate the feasibility of a cryptographically-relevant quantum computer".  

Most answers were related to fault-tolerance.

We tried "scalable fault-tolerant logical qubit" in a previous  year, but it's hard to converge on a precise notion of scalable.

Further complicating matters is that different platforms may be much more easy to scale than others once a fault-tolerant logical qubit is achieved.

 

3) 

Let me reiterate the point that it would be helpful to make more precise statements about the risk.

And 50% chance isn't in most cases the right number if discussing what date to assume for planning purposes.  e.g. a 5% chance is closer to what might be considered a borderline risk tolerance. 

So if wanting to back up one's opinion with a bet, please offer a date with 19:1 odds.

 

Also, if trying to convey a bottom-line risk (which betting odds can capture), then vague qualifiers like "Unless something unexpected happens" or "Unless there are drastic improvements in algorithms" don't realistically allow that.

Deriving a bottom-line risk estimate would require fine-grained estimates like 2% chance of 10000x improvement, 10% chance of 1000x improvement, 20% chance of 100x improvement, 50% chance of 10x improvement, etc., and estimates of the likelihood of the hardware advancing sufficiently in each of those scenarios (and that's a major simplification of the overall challenge of trying to estimate the threat timeline).

 

Best, 

Michele 

 


From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Tony Arcieri <bas...@gmail.com>
Sent: May 3, 2023 3:28 PM
To: John Mattsson <john.m...@ericsson.com>
Cc: pqc-...@list.nist.gov <pqc-...@list.nist.gov>

Subject: Re: [pqc-forum] $2050 that no quantum computer will break RSA2048 before 2050. Any takers?
--
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.

Pierre-Luc Dallaire-Demers

unread,
May 8, 2023, 3:32:49 PM5/8/23
to Michele Mosca, Tony Arcieri, pqc-...@list.nist.gov
Hi Michele,

What about elliptic curve discrete logarithms, won't the quantum-classical break-even be achieved before RSA? If there are challenges from a few parties (incl. Certicom challenges), wouldn't cheating require great amounts of coordination?

Also I have the opinion that a demonstration of fault-tolerant magic state distillation would be a huge milestone toward FTQC cryptanalysis. The time derivative that measures the increase of the number of achievable code cycles would also be an important measure. Whether we can do 1000 cycles vs 1000000 cycles in 3 years would be very informative about the expected timelines.

Best regards,

Pierre-Luc

Tony Arcieri

unread,
May 8, 2023, 4:29:26 PM5/8/23
to Pierre-Luc Dallaire-Demers, Michele Mosca, pqc-...@list.nist.gov
On Mon, May 8, 2023 at 1:32 PM Pierre-Luc Dallaire-Demers <dallair...@gmail.com> wrote:
What about elliptic curve discrete logarithms, won't the quantum-classical break-even be achieved before RSA?

That seems like a fun subject for a bet in and of itself.

My understanding is there is recent work on applying Shor's algorithm to factorization which is not immediately applicable to ECDLP which makes attacking RSA cheaper than attacking ECC at the security level of RSA-3072/256-bit ECC:

https://arxiv.org/pdf/1905.09749.pdf

Though the paper notes that you shouldn't try to draw generalizations from that:

Not all optimizations developed in this paper are directly applicable to arithmetic in elliptic curve groups. It is an interesting topic for future research to study to what extent the optimizations developed in this paper may be adapted to optimize such arithmetic operations (see Section 4.5). This paper should not be perceived to indicate that the RSA integer factoring problem and the DLP in finite fields is in itself less complex than the DLP in elliptic curve groups on quantum computers. The feasibility of optimizing the latter problem must first be properly studied.

[...]
 
Many of the optimization techniques that we use in this paper generalize to other contexts where arithmetic is performed. In particular, consider the Toffoli count for computing discrete logarithms over elliptic curves reported in [74]. It can likely be improved substantially by using windowed arithmetic. On the other hand, because of the need to compute modular inverses, it is not clear if the coset representation of modular integers is applicable. Which of our optimizations can be ported over, and which ones cannot? How much of an improvement would result? These are interesting questions for future research work.

--
Tony Arcieri

Pierre-Luc Dallaire-Demers

unread,
May 9, 2023, 1:50:07 AM5/9/23
to Tony Arcieri, Michele Mosca, pqc-...@list.nist.gov
Several optimizations were applied in this recent work: https://arxiv.org/abs/2302.06639
They have very optimistic expectations about the performance of their hardware, so more realistic resource estimations would be interesting for the surface code.
ECC-256 may be doable around >1M qubits, it depends a lot on the precise architecture of the computer.

Figure 1 of the paper (see attached) does give hope that small scale ECDLP demonstrations could happen in the range of 1E4-1E5 qubits.


Martin Musatov

unread,
Jun 29, 2023, 5:27:55 PM6/29/23
to pqc-forum, John Mattsson
Before I can reasonably answer I have one question: "What if a quantum computer is not required, would you still honor the wager?" vis a vis $2050 that RSA2048 remains unbroken on January 1, 2050.

I know 5% is a small margin, but I am not BS-ing nor AK-ing. There is a [near-term] speedup for optimization. Hint: it's not MACHINE LEARNING. It's a very human approach that would be impossible to leverage without a computer to execute.

ERROR A.I. shall not give away my trimmed wick for the sake of darkness and no lamp of it my own. 

I have plenty of oil to fill (our lamps) if you'll let me at the virgins. 

I promise you no weird travel agency arrangements like those last minute trips the children (some of them) have been taking after they piped and sang duress in the marketplace... 
==There exists a very fine line between filling a notebook with notes and performing a wide variety of repetitive tasks which are yet each unique in their instances but not their class. Like if DOG is the membership or CLASS(Y) why the specific dog (not why the breed) is the instance of a question answered, please don't ask Y.

This is situation is vastly different...often experts say lack a thoughtfulness

Mathematically, computationally--the issue of having a subgroup beneath EACH class and each unique iteration (or number) is who the hell knows if it is relevant0000 or not class currently AFAIK. 

I'm the CENTER-OF-QUANTUM no cooler nickname for any 3 or 4 (thousand or more) of us called any 1 of us...

Thee ONLY cave-in factor is if the dog is still a puppy 

(nickname for numbers we can compute (and factor)) 

or if the DOG is a GROWN GUARD DOG (one's out of reach because of massiveness). RSA 8388608 ad for our sponsor NEW double (x2_) MERSENNE PRIME numbers 4 your twister
THEY can't be proven 8600·204204000000-1to not exist completely listed on a hard-drive floating in outer-space in the future...
umm_ but we're still at 80%.... hold please....  checking factors.... computing new percentage....&*^%$&*^%$*&^
unknown noisy qubit(s) encountered !!@!!!!  WHO HAS THE HARDWARE>!!!!?
PROFESSOR, HTTplease... I promise you it will not come to that...

f i n e  p  r  i  n  t
You might need a human to pay close attention to a4 men shunned SLEW OF (incoherent irrelevant drivel) you could have just said "text'.
and chose what pieces of information are entirely relevant  (AFTER THE F__ ACT_) GRADER TEACHER.LAWN DONE errorists

You might try this... psst...

WARNING: making this text relevant to be summarized by hostiles and friendlies (or PRETTY PRETTY PLEASE
objective ENEMIES OF NOT MINE) has GOT TO BE HARDER THAN FACTORING LARGE RSA NUMBERS.

But, I don't even have to teach a computer how to do that, 

Only how to take notes (OR  HOW 2 FACTOR (puppy-dog) integers that ain't THE RUNTS theyt used to be. 

sHE can be a real (challenge) 

EYE-LENDER. 

ARM E A.C.H. 

OR NAY V-BLUE IN THE FACE2
(NECKS on the line) 

ad: Nobody builds a better stone wall than NAVY.

        HOW ABOUT 

"DRONE WASTE" painted on the sidewalk bigger than the great wall of CHINAMEN LAUGHING 

IN OUTER SPACE 
hid by ANOTHER great wall they built there while you were sleeping, Jack.

seriously should I give it up or wait and make an app (YOU'RE NOT MY ONLY CONCERN BIG BROther) 

Or should I give it away to foreigners because they are CURRENTLY likely (near-term) enemies...
I

The philosopher said 

know thyself 
 i+

but it's impossible to be sure you do, (I add very little other than to say) only you can be sure you don't. if you don't love your enemies.

Daniel Apon

unread,
Jun 29, 2023, 5:29:42 PM6/29/23
to Martin Musatov, pqc-forum, John Mattsson
Nice.

--
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.
Reply all
Reply to author
Forward
0 new messages