4
$\begingroup$

What would be telltale signs that quantum computers become imminent and sizable danger to classical cryptography in commercial applications ?

Make classical cryptography consist of symmetric algorithms (block ciphers, hashes), and asymmetric algorithms assuming hardness of factorization or discrete logarithm in $\Bbb Z_p$ or Elliptic Curve, with parameters large enough to reach security against classical algorithms run on world-class classical computers. Perhaps, assume access to all results in the field of quantum computing (even secret ones: you are CIA analyst with eyes everywhere).

I suggest "imminent" to be 2 years and "sizable" to be something worth betting for if winnings are 100 times the bet; but feel free to parametrize or change that.

Please develop rational arguments (preferably quantitative) e.g. based on categorizing what's achievable using various breeds of quantum computers, what inherently limits progress in the field, and comparison to other technical advances.


Motivation: this May 18, 2018 article quotes the director of a research lab involved in the development of quantum computers:

"Anyone that wants to make sure that their data is protected for longer than 10 years should move to alternate forms of encryption now"

and based on that source, the journalist writes:

Quantum computers will be able to instantly break the encryption of sensitive data protected by today's strongest security (..) This could happen in a little more than five years because of advances in quantum computer technologies.

$\endgroup$
  • 1
    $\begingroup$ My personal opinion: the article is a collection of rumours presenting one of many possible scenarios. What I see there is a marketing fueled sales pitch based on scaring people. Lines stating "instantly break" are not even close to the current (publically known) status quo of quantum-computer based attacks. Show me a solution to paralleling computations on a network of quantum compiters (which do not exist today) and I'll be happy to revalidate my position. Up intil then, "instant breaks" are nothing more than an unfounded lie enforcing an "omg, we're all going to die" way of thinking. $\endgroup$ – e-sushi May 21 '18 at 11:47
  • 2
    $\begingroup$ I don't believe that a good answer would be completely opinion based as the people in the QC community publish pretty heavily, as most of it is in academic circles. It would just be giving a structured scenario. As an example, coherences falls pretty had after a handful of cubits, and whenever you see that paper, the systems would be working well enough to get the 3661 cubits I need to factor AES. Of course, you then see who just ordered 1000L of He3. Most of what I see on crypto.se I consider to be structured opinions. $\endgroup$ – b degnan May 21 '18 at 12:52
  • 1
    $\begingroup$ Improving that question is discussed here. $\endgroup$ – fgrieu May 21 '18 at 18:26
  • 2
    $\begingroup$ @fgrieu Reopened for the benefit of the core of your Q — as I do understand what you're aiming at and answers might have their merit if they're indeed based on actually verifiable claims (as I personally have seen you post them in the past for example; I love those btw.) instead of the tin-foil-hatted answers we sometimes tend to see posted at Qs like this. I'm trusting the community to sort out the good from the bad if some answer goes "conspiracy" or something. I only do hope no one abuses this as a base to knock out our "opinion based" rule; but if that happens we'll take it from there. $\endgroup$ – e-sushi May 21 '18 at 20:21
  • 2
    $\begingroup$ Stuff as mundane as the cube - square law proves that car sized ants (as in the SciFi film) are scientifically impossible. QM is far trickier. Are we sure that a 100+ qbit machine is even possible in nature? What do the chaps in the quantum forum say? $\endgroup$ – Paul Uszak May 22 '18 at 20:43
4
$\begingroup$

There are three main standard quantum threats to traditional cryptography:

  1. Shor's algorithm. Spend $O(\log \ell \cdot \log \log \ell)$ quantum gates and $O(\log \ell)$ additional qubits in a quantum circuit to compute the period of a function $f$ bounded by $\ell$. The number of quantum gates to compute $f$ is about the same as the number of classical gates, and the number of qubits is about double the number of classical bits to be reversible.

    Standard examples:

    • Fix a group $G$ of order $q$, say $(\mathbb Z/p\mathbb Z)^\times$ for prime $p$, or the $k$-rational points $E(k)$ on some elliptic curve $E/k$ over a field $k$. For $g, h \in G$, define $f(x, y) := h^y g^{-x}$. If $h = g^n$ for some integer $n$, then $f(x, y) = g^{n y - x}$ and any period $(\delta, \eta)$ of $f$ satisfies $g^{n y - x} = g^{n (y + \delta) - (x + \eta)}$ for all $x$ and $y$ including zero, so that $0 \equiv n \delta - \eta \pmod q$, from which we can recover $n \equiv \eta \delta^{-1} \pmod q$. Hence by finding a period $(\delta, \eta)$ of $f$, Shor's algorithm computes discrete logs.
    • Let $n = pq$ be a product of two secret large primes $p$ and $q$. If for random $a \in \mathbb Z/n\mathbb Z$ the period of $f(x) = a^x \bmod n$ is $2r$ and $a^r \not\equiv -1 \pmod n$, then $\gcd(a^r \pm 1, n) \in \{p,q\}$, yielding a nontrivial factor of $n$. If not—if the period of $f$ is odd, or if $a^r \equiv -1 \pmod n$—then try again with another $a$. Hence by finding a period $2r$ of $f$, Shor's algorithm factors integers.


    The current record for Shor's algorithm in 2012 computed the period of $x \mapsto 4^x \bmod{21}$, which is (spoiler alert!) 3, by reducing the machine to a single qubit and a single qutrit and computing bits of the period one serially, rather than two control qubits and five work qubits as the algorithm would generally require for integers of that size to give the answer all at once.

    This record is not much of an improvement over the first report of Shor's algorithm in 2001, which computed a period of 2 or 4 for $x \mapsto a^x \bmod{15}$ using seven qubits without the qubit recycling that enabled the 2012 record to use fewer qubits.

    To scale this up to numbers of thousands of bits, we would need a much larger quantum computer than that. There are various estimates of how many qubits and quantum gates we need[cetacean needed]. Allegedly IBM has made a 50-qubit quantum computer, and Google has made a 72-qubit quantum computer, but nobody has reported successfully running Shor's algorithm on them. Evidence that quantum circuits can be scaled up to run Shor's algorithm beyond a handful of qubits to find periods larger than 4 will be a necessary first step before it threatens cryptography based on abelian hidden subgroups. The adiabatic quantum computer of D-Wave is unfit to run Shor's algorithm. But:

  2. Quantum annealing to factor by optimization. Given $n = pq$, write $n = \sum_i n_i 2^i$, $p = \sum_i p_i 2^i$, and $q = \sum_i q_i 2^i$. Knowledge of the bits $n_i$ of $n$ yields a system of quadratic constraints for the unknown bits $p_i$ and $q_i$ of $p$ and $q$. This is a system of $O(\log n)$ equations in $O(\log n)$ unknowns. Use classical computation to optimize away some of the unknown variables to reduce the system of constraints. For example, we can posit that $p_0 = q_0 = p_{\lambda-1} = q_{\lambda-1} = 1$ since the factors are odd and of known size, where $\lambda$ is the size of the factors, typically 1024 for a 2048-bit modulus. Then use quantum annealing on an adiabatic quantum computer to find the values of $p_i$ and $q_i$ minimizing $(n - pq)^2$ with $O(\log^2 n)$ qubits.

    The current records for factoring by annealing in 2018 use 94 qubits to encode this optimization problem for 376289, along with >1000 additional qubits to implement the optimization on the D-Wave 2000Q. The paper's estimate for the number of qubits to factor the current classical RSA-768 record with this method is 147456, in contrast to this ‘RSA-19’ problem taking 94 qubits—and that doesn't count the additional >1000 qubits needed to implement the program on the D-Wave machine. (It is unclear to me whether those are counted in the $O(\log^2 n)$ growth curve advertised for this method, but I assume they are.)

    One paper pointed out that other integers have been accidentally factored by the same method ‘without awareness of the authors’ of the prior method, but all this means is that the other integers turn out to have essentially the same set of constraints; it implies nothing about the cost of a high probability for success at factoring random semiprimes as chosen in RSA key generation.

    D-Wave's computers seem to be getting bigger, but to my knowledge it remains unclear whether they actually provide quantum speedup at all vs. any specialized hardware to solve optimization problems. Even if they do, it is unclear what the scaling of the time-to-solution will be as a function of the number of variables or constraints, which nobody seems to have attempted to address short of fitting a curve to small samples of experiments. Answering these questions—is quantum annealing faster than classical annealing on specialized hardware, and how does time-to-solution scale for optimization-based factoring?—is a necessary first step before this technique will even begin to threaten cryptography based on factoring.

  3. Grover's algorithm. Spend $O(2^{n/2})$ time evaluating a boolean circuit in quantum superpositions of inputs to find a preimage among $O(2^n)$ possibilities.

    There's some literature on experimental realizations[cetacean needed], including combining it with optimization-based factoring in a quantum circuit rather than on an adiabatic quantum computer[cetacean needed], but I'm out of time to bloviate about this for now.

    Mitigations for Grover's algorithm are widely known, if excessively conservative[cetacean needed], by increasing symmetric key and hash sizes. Grover's algorithm could in principle threaten factoring-based cryptography using Grover-ECM[cetacean needed], again requiring doubling of the prime sizes, but to my knowledge it doesn't improve attacks on modern elliptic-curve cryptography[cetacean needed].

$\endgroup$
  • 1
    $\begingroup$ FYI, Google's Bristlecone is claiming 72 qubits: ai.googleblog.com/2018/03/… $\endgroup$ – John Deters Jun 6 '18 at 17:58
  • $\begingroup$ Citations for newer Shor experiments: cstheory.stackexchange.com/q/37113 $\endgroup$ – Squeamish Ossifrage Jun 7 '18 at 1:01
  • $\begingroup$ Cetacean: any of an order (Cetacea) of aquatic mostly marine mammals that includes the whales, dolphins, porpoises, and related forms and that have a torpedo-shaped nearly hairless body, paddle-shaped forelimbs but no hind limbs, one or two nares opening externally at the top of the head, and a horizontally flattened tail used for locomotion. $\endgroup$ – Patriot Sep 19 at 15:06
  • $\begingroup$ @Patriot It's a joke, and a reminder that citations are needed for the specific claims that I made which I didn't bother to dig up while writing this answer. Don't just remove the reminder without actually digging up the correct citation that I intended. If you're not clear on what the author meant, ask first with a comment. A litany of misleading edits that overwhelms the site's review system is not helpful. $\endgroup$ – Squeamish Ossifrage Sep 19 at 15:10
  • $\begingroup$ @SqueamishOssifrage Sure. I did not get the joke. I thought the issue had already been resolved. I wrote you and all of the mods on chat, and I do agree with you--let the author put in references to Wikipedia, no one else. I think it is a good idea. $\endgroup$ – Patriot Sep 19 at 15:16
1
$\begingroup$

I do not believe we can have a reliable warning ~2 years in advance. First is that a significant amount of research is classified. The NSA isn't telling anyone how there research is advancing. Benyamin Netanyhu just publicly stated Israel should focus on "Quantom" research. Do you think the Mossad is sharing it's advances.

How far can the NSA be ahead of the rest of the world? a lot. Someone at IBM discovered differential cryptography and the NSA kept it secret for almost 20 years before Biham&Shamir re-discovered it.

I don't think the NSA is 20 years ahead of the world in Quantom computing, but can't be sure where they are even now.

Currently we don't know how to build quantom computers, we don't know how to put enough q-bits together and keep them coherent across enough operations. In fact we are nowhere near a practical quantum computer.

We will probably need at least one break through and some incremental improvements before we get there. Will the breakthrough be made public? don't know. If we make a break through which starts a steady Moor style growth in quantom computing (q-bits/number of coherent operations/clock speed/...) we will be able to make predictions on when modern cryptography will be at risk. Could have a few months or a few years of warning.

But maybe it takes two breakthroughs? We make the first and every panics expending the previous scenario, but we end up not progressing much until a second breakthrough comes a decade or two later.

Which is it going to be? I don't know. Don't think anyone does.

However I'm happy we are already seeking post Quantom alternatives.

*Answering because I find this of interest despite being a primarily opinion based question.

$\endgroup$
  • 1
    $\begingroup$ The question of secrecy of developments is real, serious, and hard to tackle. The question tries to sidestep it with "Perhaps, assume access to all results in the field of quantum computing (even secret ones: you are CIA analyst with eyes everywhere)". With that bold assumption, why would it be impossible to forecast progress ~2 years in advance? $\endgroup$ – fgrieu Jun 6 '18 at 17:24
  • 1
    $\begingroup$ As I said, we don't know if it takes 1 break through or two or more. And breakthroughs are hard to predict, only if we stabilize on a path of growth will predictions be possible. And we may break current crypto before growth stabilizes $\endgroup$ – Meir Maor Jun 6 '18 at 17:35
0
$\begingroup$

This is perhaps a bit trite, but I would posit that our first unequivocal warning would be irregularities in BitCoin or other crypto currencies.

$\endgroup$
  • 1
    $\begingroup$ Do you mean irregularities because the trendsetters there are fearing cryptopocalypse, or because quantum gear actually helps find bitstrings considered valuable? $\endgroup$ – fgrieu Jun 7 '18 at 5:39
  • 1
    $\begingroup$ Specifically, I'd guess that high-value wallet private keys would be able to be compromised. That would be the straw that breaks the camel's back, surely. $\endgroup$ – nsayer Jun 7 '18 at 14:45
  • $\begingroup$ I think (but that's not a crypto consideration) that credit cards are more important in the wolrd economy that bitcoin, and for this reason the "first warning" will not appear in the bitcoin community... $\endgroup$ – Ievgeni Sep 20 at 14:23
0
$\begingroup$

What telltale signs would indicate that quantum computers are about to become dangerous to classical cryptography?

There is a very pragmatic, practical, and effectively foolproof set of signs to reveal this tipping point! Watch banks, brokerage firms and the like looking for requirements that their clients adopt radically stronger encryption, namely RSA1024, then RSA2048, then RSA4096 indicating that the number of relatively stable qbits on available QC's are growing and that current modes of encryption are about to fail.

$\endgroup$
  • $\begingroup$ @ Warren A. Hall Could anyone really find a brokerage firm that still uses 1024-bit RSA? $\endgroup$ – Patriot Sep 19 at 10:58
  • $\begingroup$ The German BSI suggests a minimum of 120 bits of security for anything that's intended to last longer than 2022 or so. So actually, anyone following official recommendations will adapt 3k bit RSA sooner or later. Following a suggested policy does not really indicate some hidden knowledge about QC. You could assume this maybe, if someone switches to 1M bit RSA or similar. $\endgroup$ – tylo Sep 19 at 15:14

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