11
$\begingroup$

I wonder how the world will come to know that scalable, fully fault-tolerant quantum computers capable of running Shor's algorithm have arrived. The day when this happens has been referred to as "Q-Day".

If this information gets out, especially if Q-Day arrives well before the world converts to post-quantum crypto, then the implications for security and commerce will likely be enormous. Maybe honest actors will work to schedule the announcements by slowly releasing RSA challenge factors, over the course of a year or so, to give the world a heads-up that RSA's writing is on the wall. Or, there could be dishonest actors acting maliciously to attack and siphon off dormant bitcoin wallets, for example.

How will the world learn that scalable, fully fault-tolerant quantum computers capable of running Shor's algorithm on cryptographically relevant keys have arrived?

Will it be with a bang or with a whimper? Has this been gamed out in any literature?

Improve this question
$\endgroup$
10
  • 9
    $\begingroup$ It's possible the first CRQCs will be owned/operated by a nation state and thus nobody will know except them as they'll try to keep it under wraps. See Google's threat model, for example. $\endgroup$
    – samuel-lucas6
    Commented Apr 2 at 16:52
  • 4
    $\begingroup$ An interesting related question would be “how could someone prove to the public that they own a cryptographically-relevant quantum computer?” $\endgroup$
    – Tjaden Hess
    Commented Apr 3 at 1:24
  • 1
    $\begingroup$ One plausible answer would be to chose a 2048-bit prime p by some “nothing up my sleeve” construction and then post the discrete log of H(“hello”) % p with base H(“world”) % p. It’s easier to transparently choose a DSA modulus than an RSA modulus - of course this doesn’t rule out novel classical attacks on DL. You could do a similar test over popular elliptic curves $\endgroup$
    – Tjaden Hess
    Commented Apr 3 at 1:30
  • 1
    $\begingroup$ @TjadenHess another option that has been explored is for classical skeptics (Vicky) to provide a semiprime $N$ to a quantum computer (Peggy), who then evaluates $f(x)=x^2\bmod N$ in superposition as $|x\rangle|f(x)\rangle$, measuring the second register in the computational basis to report a $y=f(x_1)=f(x_2)$ for preimages $(x_1,x_2)$, while measuring the first register in the Hadamard basis to report a string $d$ such that $d\cdot (x_1 \oplus x_2)=0$. The thinking is that evaluating $x^2\bmod N$ is much easier than evaluating $a^x\bmod N$... $\endgroup$
    – Mark S
    Commented Apr 3 at 12:30
  • 7
    $\begingroup$ We need some better branding here, because Q-day really sounds like a QAnon related conspiracy. $\endgroup$
    – Kaia
    Commented Apr 3 at 20:44

4 Answers 4

Reset to default
20
$\begingroup$

How will the world learn that scalable, fully fault-tolerant quantum computers capable of running Shor's algorithm have arrived?

Well, one thing to note is that cryptanalysis is not the only thing a Real Quantum Computer would be good for. Another thing would be analyzing chemical reactions; a chemical reaction between molecules is an inherently quantum process, and so a Quantum Computer would be expected to model it far better than a conventional computer.

And, I expect that:

  • Modeling a chemical reaction should be easier than Shor's; I believe that fewer qubits are involved, and the circuit depth is far smaller.

  • Insights into what happens during a chemical reaction may translate into being able to better optimize an industrial chemical engineering process, and even a modest optimization can translate to billions of dollars/euros savings.

  • Chemical manufacturing companies would have little reason to keep their use of Quantum Computers secret (and would not be allowed to hide their increased profits and/or reduced costs). I would assume that they would loudly proclaim the message "We are now greener when making fertilizer".

Hence, until we see significant advancements in the chemical engineering space, I don't believe that Q-day has arrived yet.

(All this IMHO)

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Thanks! I agree with everything you said but I wonder about a dark-horse that enters the race by secretly and mysteriously posting RSA challenge factors onto the blockchain or something... $\endgroup$
    – Mark S
    Commented Apr 2 at 16:31
  • 1
    $\begingroup$ @MarkS: actually, I wouldn't be worried about someone anonymously posting a factorization. What would be a more credible concern if a TLA were to gain access to a CRQC before anyone else (they wouldn't publicize the fact that they can read classically encrypted traffic). I do believe that, because a Chemically Relevant Quantum Computer would be significantly easier (and would likely be publicly visible), the concern is lesser, but it would be still be a concern. $\endgroup$
    – poncho
    Commented Apr 2 at 18:10
  • 2
    $\begingroup$ “If computers that you build are quantum / Then spies of all factions will want 'em. / Our codes will all fail, / And they'll read our email, / Till we've crypto that's quantum, / and daunt 'em.” - Jennifer and Peter Shor, c. 1996 $\endgroup$
    – Mark S
    Commented Apr 2 at 21:03
  • $\begingroup$ @MarkS I realise that the Shors are blowing their own trumpets, but we've been using quantum resistant one time pads for decades. $\endgroup$
    – Paul Uszak
    Commented Apr 3 at 12:12
  • 3
    $\begingroup$ @poncho, I have not voted either way, but I interpret OP's question such that the aspect of "crypto" is much more heavily weighted than "quantum". I.e., my (non-written, by OP) assumption is that a "crypto" agent gets access to a quantum computer before any other (i.e., before something benign as a purely industrial company). With this assumption, your answer is conceivable but not getting at the meat of the issue... $\endgroup$
    – AnoE
    Commented Apr 4 at 12:40
11
$\begingroup$

Frame challenge: "Q-Day" is a mental shortcut for what is not actually a sudden event.

Quantum computing, nuclear fusion, AI, flying cars - there's a number of technologies that have been "just around the corner" for decades.

It is highly likely that "Q-Day" will actually be "Q-Year" or something like that. That over the course of several years we inch closer and closer, make small steps here and there, solve this issue and that, and slowly, slowly, we get there.

It is highly improbably that someone comes out of the woods one day and announces a full-blown quantum computer. Instead, there will be many announcements, by many research institutes, over the course of the next decade or two. Heck, there was one today.

That means that the transition to post-quantum encryption - which has already started - can progress equally slowly, and as we get closer, those who haven't already moved will feel more and more that they should.

By the time the RSA-Quantum-Breaker(tm) arrives, there will be only a few left who are really lagging very much behind.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ The answer is short on justification for "the next decade or two". For the record, work on energy production by nuclear fusion started circa 1950. $\endgroup$
    – fgrieu ♦
    Commented Apr 4 at 16:48
  • $\begingroup$ Whilst I agree that progress will be gradual, this answer fails to acknowledge that people are inevitably working on CRQC development in secret. If they were the first to succeed, they could use them in an attack and get discovered, which could mean an announcement out of the blue. Furthermore, the 'store now, decrypt later' attack is a problem now; the longer you leave migration, the more information there is that can theoretically be compromised. And lots of companies use legacy hardware somewhere and have been slow or failed to migrate with previous migrations. $\endgroup$
    – samuel-lucas6
    Commented Apr 4 at 17:48
  • 1
    $\begingroup$ @samuel-lucas6 that is true but too short and would justify its own question and answer, though much of the answers would be based on speculation. I'm not currently as active in crypto as I used to be, but my understanding is that while the NSA was assumed to be about a decade ahead of the public, that has largely disappeared. They (and their counterparts in other countries) are probably still at the bleeding edge, but not years ahead. $\endgroup$
    – Tom
    Commented Apr 5 at 6:16
  • $\begingroup$ @samuel-lucas6 also, while SNDL is a serious theoretical problem (and I'm sure is practiced at large scale) for most companies it isn't a serious risk. Diplomats and governments certainly, they have secrets they don't want to reveal at least until everyone involved is dead, but only a few types of companies (e.g. insurances) have things that are still valuable in 10 years. I make a point of looking at SNDL whenever I do risk analysis and it rarely turns out to be a major risk. $\endgroup$
    – Tom
    Commented Apr 5 at 6:19
  • $\begingroup$ @Tom I agree they're probably not that far ahead. As for SNDL, only highly sensitive data is likely to be targeted, at least to start with. However, things like trade secrets and personal data are still at risk, and lots of companies are storing personal data. Will they be held responsible and fined if encrypted data is compromised because they failed to migrate to PQC quick enough? $\endgroup$
    – samuel-lucas6
    Commented Apr 5 at 12:32
6
$\begingroup$

I'm a professional cryptographer for a major financial company, and I've been doing crypto professionally for 37 years. If anyone can develop a QC capable of factoring big key-moduli, it'll be a well-funded national cyberwarfare group, like the NSA or China's APT groups. There's no way that any cyberwar group will announce its QC capabilities, period. We won't know until it's too late.

That said, I very much doubt that such large QC's will ever get built, because of the quantum noise problem, and because of other problems. We'll still have to prepare to move to post-quantum ciphers, because the financial industry's regulators will require PQC as a sober precautiion.

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ "I very much doubt that such large QC's will ever get built, because of the quantum noise problem, and because of other problems."; that may very well be true, but some of us are uncomfortable with making that a security assumption... $\endgroup$
    – poncho
    Commented Apr 4 at 15:39
  • 1
    $\begingroup$ If you ask me, the financial industry's regulators should focus on what the real problems are: integrity of computing environments, and robust imputability that can't be broken by the sysops. $\endgroup$
    – fgrieu ♦
    Commented Apr 4 at 16:51
3
$\begingroup$

How do we know it hasn't already? Perhaps I have a working quantum computer in my basement that is currently breaking a thousand RSA keys a second? Can you prove that I have not?

Well, the public will know when:

  • Someone says they built a quantum computer that can break RSA and demonstrates it.
  • There is credible evidence that some organization can break RSA.
  • A technological breakthrough is publicized that makes the construction of an RSA-breaking quantum computer a trivial endeavor.
Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ But someone might have broken RSA classically so the second bullet points is problematic $\endgroup$
    – kodlu
    Commented Apr 3 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.