Are we having fun yet?
-
@sophieschmieg from a quick look, this seems a bit... audacious?
under plausible assumptions, the runtime for discrete logarithms on the P-256 elliptic curve could be just a few days for a system with 26,000
physical qubits@tomgag these are not the only quantum physicists that have said that recently.
-
Are we having fun yet?
Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits
Abstract page for arXiv paper 2603.28627: Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits
arXiv.org (arxiv.org)
@sophieschmieg When people question the aggressive quantum readiness timelines given that 100 qubit computers are all we have today, I have to explain that it's not just a matter of building a computer with a million qubits, but that researchers are still publishing optimizations that may cut that by a factor of 10, or 100, or more. And we simply don't know if or when they'll figure out something better.
-
@sophieschmieg On the one hand a weird focus on cryptocurrency is weird, on the other if we managed to break all of the cryptocurrencies with relatively small/cheap (relatively!) quantum computers I suspect I would laugh so hard I hurt myself. And then I'd send pastries to whoever worked out how to do that because they 100% deserved them.
-
@sophieschmieg When people question the aggressive quantum readiness timelines given that 100 qubit computers are all we have today, I have to explain that it's not just a matter of building a computer with a million qubits, but that researchers are still publishing optimizations that may cut that by a factor of 10, or 100, or more. And we simply don't know if or when they'll figure out something better.
It's that, plus the fact that the day you migrate to PQC, all your *future* comms are safe, but all your past comms *will* be vulnerable some day.
If those comms contain other key / authentication materials for other parts of the system, then the Adversary will gain access to those as well.
That, and the unfortunate reality that a lot of orgs will drag their feet on this and you'll have vulnerable crypto in prod probably even after the first utility scale machines.
-
@sophieschmieg When people question the aggressive quantum readiness timelines given that 100 qubit computers are all we have today, I have to explain that it's not just a matter of building a computer with a million qubits, but that researchers are still publishing optimizations that may cut that by a factor of 10, or 100, or more. And we simply don't know if or when they'll figure out something better.
@targetdrone @sophieschmieg if we haven't learned from Y2K that preparing for shit quietly in the background pays off, we haven't learned anything.
-
It's that, plus the fact that the day you migrate to PQC, all your *future* comms are safe, but all your past comms *will* be vulnerable some day.
If those comms contain other key / authentication materials for other parts of the system, then the Adversary will gain access to those as well.
That, and the unfortunate reality that a lot of orgs will drag their feet on this and you'll have vulnerable crypto in prod probably even after the first utility scale machines.
@emc2 @sophieschmieg On the flip side, quantum attacks will remain expensive for a long time. Nobody's going to spend coin to crack rabbitfanciersforum.com when they could instead profit from cracking verylargebank.com.
If I were an attacker, I'd go after the CAs like digicert et al. With a signing key I would forge any site certs I wanted. PQ preparedness won't stop this until the bad CA certs are out of everyone's trust stores.
-
@emc2 @sophieschmieg On the flip side, quantum attacks will remain expensive for a long time. Nobody's going to spend coin to crack rabbitfanciersforum.com when they could instead profit from cracking verylargebank.com.
If I were an attacker, I'd go after the CAs like digicert et al. With a signing key I would forge any site certs I wanted. PQ preparedness won't stop this until the bad CA certs are out of everyone's trust stores.
@targetdrone @emc2 yeah, CAs and CT logs are the keys you want.
-
@emc2 @sophieschmieg On the flip side, quantum attacks will remain expensive for a long time. Nobody's going to spend coin to crack rabbitfanciersforum.com when they could instead profit from cracking verylargebank.com.
If I were an attacker, I'd go after the CAs like digicert et al. With a signing key I would forge any site certs I wanted. PQ preparedness won't stop this until the bad CA certs are out of everyone's trust stores.
Yes, it will be stuff like "we're going to spend the next two months cracking the key agreement on this intercept from such and such embassy we intercepted in 2007", probably for decades after the first utility scale machines exist.
However, I could see seemingly lower-value targets getting hit in order to set up aggregation, supply chain, or other attacks.
-
Yes, it will be stuff like "we're going to spend the next two months cracking the key agreement on this intercept from such and such embassy we intercepted in 2007", probably for decades after the first utility scale machines exist.
However, I could see seemingly lower-value targets getting hit in order to set up aggregation, supply chain, or other attacks.
@emc2 @targetdrone yeah. In fact I'm worried that in some sense slower and less accessible CRQC paradoxically pose a greater risk to the common people: if, at the extreme but imaginable end, it takes two months to break a key, and you only have one quantum computer, exploiting SNDL for random cables very quickly becomes unsatisfying. And breaking fairly few supply chain keys (CA, CT logs, identity providers, software signing etc) becomes very tempting, even if it risks giving away that you have a CRQC at your disposal. And those supply chain risks in turn put everyone at risk, not just some limited spy games between embassies.
-
@targetdrone @sophieschmieg if we haven't learned from Y2K that preparing for shit quietly in the background pays off, we haven't learned anything.
A lot of people think Y2K was a hoax because there was no huge apocalyptic disaster.
For some reason they find it difficult to believe that the huge apocalyptic disaster would have happened if not for the large, costly effort to fix the bugs *before* the big day.
-
Yes, it will be stuff like "we're going to spend the next two months cracking the key agreement on this intercept from such and such embassy we intercepted in 2007", probably for decades after the first utility scale machines exist.
However, I could see seemingly lower-value targets getting hit in order to set up aggregation, supply chain, or other attacks.
@emc2 @sophieschmieg Breaking a 2048-bit RSA key will likely take a year or more of quantum compute time initially. Using the going rate of $98USD/minute for access to an (inadequate) 100-qubit machine, we can ballpark an initial cost of 8 or 9 figures.
You'd have to be absolutely certain of the value of the key you are cracking to realize a return on that kind of investment.
-
@emc2 @sophieschmieg Breaking a 2048-bit RSA key will likely take a year or more of quantum compute time initially. Using the going rate of $98USD/minute for access to an (inadequate) 100-qubit machine, we can ballpark an initial cost of 8 or 9 figures.
You'd have to be absolutely certain of the value of the key you are cracking to realize a return on that kind of investment.
I can't go into too much detail (propin, ndas, etc) but the actual cost of a utility scale machine will be in the hundreds of thousands per day. The time will vary depending on the architecture, but you're looking at order months to hit the P-256 curve. RSA is more of a moving target, but expect similar.
-
@emc2 @targetdrone yeah. In fact I'm worried that in some sense slower and less accessible CRQC paradoxically pose a greater risk to the common people: if, at the extreme but imaginable end, it takes two months to break a key, and you only have one quantum computer, exploiting SNDL for random cables very quickly becomes unsatisfying. And breaking fairly few supply chain keys (CA, CT logs, identity providers, software signing etc) becomes very tempting, even if it risks giving away that you have a CRQC at your disposal. And those supply chain risks in turn put everyone at risk, not just some limited spy games between embassies.
This is very true, and in fact I would expect targeting more public infrastructure that would allow massive disruption (e.g. Central banks, public utilities in major cities, CAs, etc) to be a better ROI, if you're after disruptive effects.
-
Oh, and in case you weren't having enough fun, here are some updated resource estimates for running Shor's on elliptic curves, unfortunately weirdly focused on cryptocurrencies.
Fun fact: I almost found a soundness problem in that zero knowledge proof that was based on a quine. Unfortunately the circuit cannot produce quines.
And now also on Ars Technica:
Quantum computers need vastly fewer resources than thought to break vital encryption
No, the sky isn't falling, but Q Day is coming, and it won't be as expensive as thought.
Ars Technica (arstechnica.com)
-
A lot of people think Y2K was a hoax because there was no huge apocalyptic disaster.
For some reason they find it difficult to believe that the huge apocalyptic disaster would have happened if not for the large, costly effort to fix the bugs *before* the big day.
@argv_minus_one In fairness, for people who only have any memory of the 21st century I can understand how the idea of society coming together at scale and spending resources to tackle a foreseeable problem before it becomes a crisis might seem farfetched.
@odr_k4tana @targetdrone @sophieschmieg -
@argv_minus_one In fairness, for people who only have any memory of the 21st century I can understand how the idea of society coming together at scale and spending resources to tackle a foreseeable problem before it becomes a crisis might seem farfetched.
@odr_k4tana @targetdrone @sophieschmiegSociety didn't come together at scale. Society, for the most part, was panicked that the end of the world was nigh.
Business leaders are the ones who came together, presumably because they didn't want their businesses to abruptly screech to a halt on 2000-01-01, and hired an army of programmers to fix the bugs.
-
Society didn't come together at scale. Society, for the most part, was panicked that the end of the world was nigh.
Business leaders are the ones who came together, presumably because they didn't want their businesses to abruptly screech to a halt on 2000-01-01, and hired an army of programmers to fix the bugs.
Perhaps it's easier for business leaders to sigh and loosen the purse strings when the disaster (1) is absolutely certain to happen, and (2) will happen at an exact predetermined time.
There's no rationalizing inaction with “it'll be the next CEO's problem” when you know for sure exactly when it will happen and therefore exactly whose problem it will be.
-
@ar1 the timeline got moved in substantially. Of course things can go wrong for the physicists, but 3 years seems feasible now.
@sophieschmieg ok. Reading up on it, I think I now understand better.
-
@lcamtuf @sophieschmieg @dangoodin
If we train LLMs on encrypted data, they will decrypt everything. It might not be the original plaintext, but it will make sense for most people.You may E2E the conversation with your mom, but everyone knows how those things go, right? With a little context from your social media profiles, there are no more secrets.
-
Oh, and in case you weren't having enough fun, here are some updated resource estimates for running Shor's on elliptic curves, unfortunately weirdly focused on cryptocurrencies.
Fun fact: I almost found a soundness problem in that zero knowledge proof that was based on a quine. Unfortunately the circuit cannot produce quines.
@sophieschmieg has anyone written a description of the zero knowledge proof for people with B.S. level mathematics education? I will attempt to read the paper but would love to read anything by experts
