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
  • 1
    $\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
3
$\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$
0
$\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$
  • $\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
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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