102

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?

  • 12
    1) Yup, I wouldn't even be surprised if they had a secret department of fortune telling... – Tobias Kienzler Jan 3 '14 at 14:16
  • 1
    Best to use OTP -in real world and for the virtual world use symmetric algorithms + 256bit keys. look at this theguardian.com/world/2013/sep/05/… – Johny Jan 3 '14 at 18:02
  • 2
    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. – November Jan 3 '14 at 20:39
  • 1
    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. – Mike Samuel Jan 3 '14 at 22:49
  • 6
    @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. – Konrad Rudolph Jan 5 '14 at 16:38
146

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...

  • 6
    +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... – Shadur Jan 3 '14 at 16:22
  • 11
    +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 – Tobias Kienzler Jan 3 '14 at 16:34
  • 3
    @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. – Thomas Pornin Jan 3 '14 at 18:02
  • 2
    @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 – Tobias Kienzler Jan 4 '14 at 8:41
  • 3
    @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). – Thomas Pornin May 5 '17 at 12:53
7

Quantum computing will make most dramatic impact on asymmetric encryption, but symmetric algorithms are considered safe with a large enough key size (256 bits). So, yeah, we'll have to reinvent x509/SSL by the time quantum computing really takes off (which is a large enough TODO), but there will be large areas of cryptography that will remain relatively safe.

http://en.wikipedia.org/wiki/Post-quantum_cryptography http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf

5

When Cryptographers speak about quantum computer and post-quantum cryptography,actually they speak about power of Shor's algorithm in factoring numbers,so hard problems based on factoring number that are used for creating cryptosystems are broken with Shor's algorithm(quantum computer) so RSA,DSA,ELGamal,Diffie-Hellman Key Exchabge,ECC are vulnerable to Quantum Computing!

In public key cryptography,three schemes are quantum-secure:

  1. Lattice based cryptography like NTRUEncrypt;based on lattices
  2. code-based cryptography like McEliece cryptosystem;based on information theory
  3. multivariate cryptography like Hidden Fields Equations

and in symmetric encryption like AES,if you choose a long key;you are safe against quantum computer and NSA!

for future reading:Quanta magazine link and post-quantum cryptography book

-1

1-time pad remains the strongest, uncrackable (if used properly) encryption. Of course, you DO have to swap pad face to face, but I reckon 95% of people who require this level of security WILL meet before setting up secure communications.

Just specifying which 256-bit key to use for a particular message works perfectly and is used by the security services.

  • 6
    This doesn't explain which types of encryption are not breakable by quantum computers, and so does not actually answer the question. – Xander Mar 14 '15 at 19:37
  • @Xander this answer says that the One-Time Pad method is unbreakable, which is a correct statement. – Count Iblis Mar 7 '16 at 16:02
  • 2
    I don't understand why this answer mentions 256-bit keys. Encrypting a 1024-bit plaintext with a 256-bit key is not using a OTP. – A. Darwin May 2 '16 at 18:22
-4

For added protection against the NSA, encrypt using AES chain block cipher mode, then encrypt the cipher text (the result from the first encryption) again, and repeat as many times as you can afford to repeat. The NSA would probably try brute force searching to go through the search space, and figure out they've cracked the code by determining the entropy of the result for each of the keys they test. They know when to stop when they see meaningful text as the result. By encrypting several times, you make it harder for them to determine when they have cracked a code because if they did try the right key, then they would see jumble as the result, almost indistinguishable from the results of the incorrect keys. As you increase the number of re-encryptions, the difficulty of cracking encrypting content becomes more difficult. The NSA will lose its mind trying to figure out when they have cracked the code.

Software like TrueCrypt can do multiple encryption for you. But beware of naive encryption that simply runs in "Electronic Code Book" (ECB) mode. You will need encryption that runs in one of the more sophisticated modes like "Chain Block Cipher" or "Cipher Feedback." Yes, a quantum computer would make it easier for the NSA to go through the possible keys to try. But by encrypting multiple times (with a DIFFERENT key for each encryption repeat of course), you make the search space difficult by a factor of the key length. Hopefully this helps you keep your stuff out of the NSA's reach.

  • 6
    The implications of applying multiple layers of encryption can be quite complex and in the worst case reduce the individual layers' security - take for example XORing the entire message twice - you end up with the original message! And even if you use two different keys, it's still equivalent to XORing with one entirely different key. It's of course more complex with AES, but you'd really do yourself a favour by increasing the key size instead... – Tobias Kienzler Jan 4 '14 at 8:46
  • @TobiasKienzler That only applies to certain types of ciphers. For stream ciphers, as long as the nonce is different, everything is fine. For (most) block ciphers, it doesn't even matter if the key is different or not, though of course if the key is the same, you get no extra security. For something like AES, it is totally safe to do multiple encryption, it's just usually kinda silly and unnecessary. – forest Apr 17 '18 at 12:28
  • @forest Doing something silly and unnecessary is unsafe, since you waste computational resources on something that doesn't truly increase security when appropriate usage of said resource could – Tobias Kienzler Apr 17 '18 at 12:31
  • @TobiasKienzler That is true. The increase in complexity can lead to bugs. I just meant that it was not unsafe in most cases in a purely cryptographic sense. – forest Apr 17 '18 at 12:33

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.