Quantum computer code cracking

Question

everyone! I don't know a whole lot about the fields of encryption or quantum computing, but I've read a lot of articles on the subjects and that is prescisley what caused this question. I've been a little scared about the whole NSA quantum computer that is build for the sole purpose of cracking encryption codes. I am fairly certain that they wouldn't use that power to get into random civilians' information, but if they did how hard would it be to block them out?

According to the numbers I've seen this computer could crack a typical encryption code within a little more than a week. And I recall seeing that a typical encryption key used in a consumer application is either 64 or 128 bits (or bytes?) long. I'm sorry if I'm getting these numbers wrong. Now, a week is an awful long time to to wait to crack a code (but wickedly better than with conventional computers), so they wouldn't waste their time on the password hash for your Facebook account. But say they did, wouldn't it be easy to overwhelm that system? According to mathematics the total number of time it would take to break the code would double with every bit longer the code is, and multiply by 256 with every byte. So, assuming a computer that could crack a 64bit code in up to a week, it would take 3.54^17 years to crack a 128 bit one.

Is this true? And if it is, then wouldn't this make the NSA computer useless? Because anyone that the angency would want to hack into could simply just increase the length of their encryption keys.

Thanks for any insight on the matter, and sorry if I have my facts wrong.

Answer 1

First of all, I seriously doubt that anyone would have a working quantum computer capable of doing anything useful in the foreseeable future (let's say 10 years). Even if someone does construct a "quantum computer", it will probably be quite useless, and it will take several years more until it can be used to, say, crack codes.

The quantum speedup for breaking symmetric encryption is quadratic: if a single decryption takes time $T$ and there are $N$ bits in the key (usually $N\geq128$ nowadays, unless you're using DES which has $N=56$), then a classical computer will take $2^NT_{\text{classic}}$ time while a quantum computer will take $O(2^{N/2}T_{\text{quantum}})$ time using Grover's algorithm (as far as I understand). In terms of real-world time, we expect $T_{\text{quantum}}$ to be several orders of magnitude larger than $T_{\text{classic}}$, at least at first. Decrypting $2^{64}$ blocks in "quantum speed" will take a lot of time, so quantum computing doesn't seem to break symmetric encryption, barring any weaknesses which enable one to use a smarter algorithm than the naive one.

The story is different for public-key encryption, though again, quantum computers capable of doing anything interesting are still far into the future. Shor's algorithm can be used to factor integers, thus breaking RSA. The algorithm also applies for the discrete log problem, even on elliptic curves. This is problematic for other public-key cryptosystems. You can check out this survey for some quantum-resistant protocols.

Answer 2

working QM computers with superior performance over classical computers are nowhere near reality even for three-letter multibillion-dollar secret government agencies and probably wont be for many years (despite large sums of research funding spent over more than a decade). this relatively recent highly-researched paper by an expert in the field serves as a useful & very cold/harsh "reality check" in the area.

• State of the art and prospects for quantum computing Dyakonov

This is a brief review of the experimental and theoretical quantum computing. The hopes for eventually building a useful quantum computer rely entirely on the so-called "threshold theorem". In turn, this theorem is based on a number of assumptions, treated as axioms, i.e. as being satisfied exactly. Since in reality this is not possible, the prospects of scalable quantum computing will remain uncertain until the required precision, with which these assumptions should be approached, is established. Some related sociological aspects are also discussed. .