What kinds of encryption are _not_ breakable via Quantum Computers?

  • There's the recent article NSA seeks to build quantum computer that could crack most types of encryption. Now I'm not surprised by the NSA trying anything1, but what slightly baffles me is the word "most" - so, what encryption algorithms are known and sufficiently field-tested that are not severely vulnerable to Quantum Computing?

    1) Yup, I wouldn't even be surprised if they had a secret department of fortune telling...

    Best to use OTP -in real world and for the virtual world use symmetric algorithms + 256bit keys. look at this http://www.theguardian.com/world/2013/sep/05/nsa-how-to-remain-secure-surveillance

    Quantum computers are still a ways off. The concept relies on using bits, that when unobserved, are both 1 and 0 and so able to calculate with all the values that can be represented in the given space -- with one calculation. As romantic as this sounds, I have yet to hear of a way to calculate with this bits while leaving them unobserved.

    Don't assume that just because an organization the size of the NSA is trying to build something that they expect to successfully deploy one anytime soon. Because arms-races are races, often an organization will research something because they don't want to be just starting out when their competitors are deploying one. If the NSA builds up a brain-trust of people who know about quantum computing then they might be able to deploy one ahead of their competitors, and are less likely to be caught flat-footed.

    My concern is not the NSA, who might just as well use some less pleasant meatworld methods to obtain one's secrets, but rather the implications of QC in general

    Why wouldn't quantum computers also enable correspondingly stronger encryption?

    @mirimir Who claimed that? Of course there's Quantum Cryptography, but even once available not everyone will be able to afford it I assume, so it's still important to know what classical encryption one can rely upon even if potential eavesdroppers have Quantum Computers

    @November Slightly modifying this nice Gedankenexperiment, assume a friend of yours went outside before it got cold. Neither you or they know how many gloves (if any) they took with them, but both know where the remaining ones would be; and that, due to the severe cold, your friend would return home for the remaining glove(s) once they noticed some were missing. Assume the same for a friend your friend wanted to meet outside. Now observe whether some of their gloves are at home - and voilà you can determine whether they met outside or come home

    @November Your knowledge is outdated. Computations on qbits *have* been performed. Just not very many. But there’s nothing “romantic” about this concept, it’s been demonstrated in practice.

    Thanks for correcting me. This is very exciting, do you have a link that explains this more in-depth?

    @November This just came out: http://arxiv.org/pdf/1512.02206v1.pdf It is a bit technical and requires a quite a bit of knowledge to be usable, but I guess most people here are :-)

  • As usual, journalism talking about technical subjects tends to be fuzzy about details...

    Assuming that a true Quantum Computer can be built, then:

    • RSA, and other algorithms which rely on the hardness of integer factorization (e.g. Rabin), are toast. Shor's algorithm factors big integers very efficiently.
    • DSA, Diffie-Hellman ElGamal, and other algorithms which rely on the hardness of discrete logarithm, are equally broken. A variant of Shor's algorithm also applies. Note that this is true for every group, so elliptic curve variants of these algorithms fare no better.
    • Symmetric encryption is weakened; namely, a quantum computer can search through a space of size 2n in time 2n/2. This means that a 128-bit AES key would be demoted back to the strength of a 64-bit key -- however, note that these are 264 quantum-computing operations; you cannot apply figures from studies with FPGA and GPU and blindly assume that if a quantum computer can be built at all, it can be built and operated cheaply.

    • Similarly, hash function resistance to various kind of attacks would be similarly reduced. Roughly speaking, a hash function with an output of n bits would resist preimages with strength 2n/2 and collisions up to 2n/3 (figures with classical computers being 2n and 2n/2, respectively). SHA-256 would still be as strong against collisions as a 170-bit hash function nowadays, i.e. better than a "perfect SHA-1".

    So symmetric cryptography would not be severely damaged if a quantum computer turned out to be built. Even if it could be built very cheaply actual symmetric encryption and hash function algorithms would still offer a very fair bit of resistance. For asymmetric encryption, though, that would mean trouble. We nonetheless know of several asymmetric algorithms for which no efficient QC-based attack is known, in particular algorithms based on lattice reduction (e.g. NTRU), and the venerable McEliece encryption. These algorithms are not very popular nowadays, for a variety of reasons (early versions of NTRU turned out to be weak; there are patents; McEliece's public keys are huge; and so on), but some would still be acceptable.

    Study of cryptography under the assumption that efficient quantum computers can be built is called post-quantum cryptography.


    Personally I don't believe that a meagre 80 millions dollars budget would get the NSA far. IBM has been working on that subject for decades and spent a lot more than that, and their best prototypes are not amazing. It is highly plausible that NSA has spent some dollars on the idea of quantum computing; after all, that's their job, and it would be a scandal if taxpayer money did not go into that kind of research. But there is a difference between searching and finding...

    +1, and wish I could give you +10 just for the last two sentences. With all the scandals about their abuses it's sometimes easy to forget that when all's said and done being able to spy on people is their *job* and what we're objecting to is their lack of restraint when doing it...

    +1 - Of course you might consider that with 80 million dollars, the NSA could just hire goons to beat private keys out of most targets... Then again they could have forced IBM and others to "volunteer" in providing their most secret research progress so far

    @Thomas Pornin Is the complexity of searching a space decreased due to the uncertainty principle? I might be way off.....

    @Rell3oT: the idea is that a qubit is a superposition of several states, and thus, _to some extent_, with one operation, several computations are done simultaneously. The uncertainty principle is another, rather unrelated expression of the fact that at the quantum level, what we think of as "matter" actually behaves like a probability distribution.

    Okay Thank you @ThomasPornin . What you described is what I thought the uncertainty principle was. Apparently I need to brush up...

    Don't all this mean that if RSA can be broken that all TLS sessions with certificates are essentially broken as RSA is used to negotiate a symmetric key at the beginning of the session? Can we still have PFS?

    @Rell3oT Uncertainty boils down to that it is not sufficient to exploit the superposition of states but that you have to do it in a way that you can afterwards measure the entire result without changing the already measured part of it - e.g. if one bit were encoded in the x-coordinate and another one in that direction's momentum, you might still be screwed since measuring momentum (sufficiently precise) will _retroactively_ change the x-coordinate (maximum possible precision) you just measured and vice versa. Btw, check out http://physics.stackexchange.com ;)

    @Matrix RSA (or DSA) is used for the server to identify itself, the key negotiation uses Diffie-Hellman. But since that relies on the discrete logarithm just as DSA does, I guess it is just as vulnerable to Quantum Computing. However I'd be surprised if there weren't a way to use/modify the less QC-vulnerable methods for PFS

    And what if the encryption was done on a quantum computer as well?

    @Jojo01: I think some encryption algorithms designed to run on quantum computers have been defined (I don't recall the details at the moment). They should resist attackers with quantum computers, but they also require a quantum computer to be used at all, and given the lack of availability of quantum computers right now, we cannot test them. Let's say they are an interesting intellectual construction that _might_ be useful in a future world where every single computer and smartphone is a quantum computer.

    @ThomasPornin Yeah, i think that quantum computing will improve account security, because the big companies will most likely be using quantum computers, that your typical hacker doesn't have. Of course when quantum computing gets to consumer lever, that advantage is lost and the situation goes back to zero.

    What about Serpent? I've read it won't be affected either.

    @skan: Serpent is a symmetric encryption algorithm; what I say about AES applies equally well to Serpent. In effect, it means that Serpent encryption with a 128-bit key could be broken with about 2^64 operations on a quantum computer (2^64 is already a very substantial amount on a classical computer).

    Having dealt with IBM a lot, it's my suspicion that they developed a quantum computer decades ago, but nobody can find the link for it on their website.

    "note that these are $2^64$ quantum-computing operations": also these operations must be sequential, meaning that your quantum computer has to be really fast ($2^64$ nanoseconds > 500 years). With $K$ parallel quantum computers you get a small speed up, but you still need time $\frac{2^64}{\sqrt{K}}$. See https://quantumcomputing.stackexchange.com/a/4538/5047

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM