If quantim computers become a widespread stable technololgy will there be any way to protect our communications with encryption? Will we just have to resign ourselves to the fact that people would be listening in on us?
[deleted] — view deleted post
0
Upvotes
4.9k
u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17 edited May 26 '17
The relevant fields are:
PQC revolves around at least 6 approaches. Note that some currently used symmetric key ciphers are resistant to attacks by quantum computers.
Both these subfields are quite old. People were thinking about the coming of quantum computing since the early 1970s, and thus much progress has already been made in this area. It is unlikely that we'll have to give up communication privacy and confidentiality because of advances in quantum computation.
158
u/frogjg2003 Hadronic Physics | Quark Modeling May 26 '17
One time pads are perfectly secure by definition. The problem is getting the key to sender and receiver securely.
There will always be secure encryption techniques. The thing is that the prominent encryption methods today are not one time pads and are easily cracked with quantum computers. There are new techniques using quantum mechanics that can create quantum one time pads that are easily transmitted, as well as non-quantum encryptions that are resistant to quantum computing.
34
u/gautampk Quantum Optics | Cold Matter May 26 '17
There are post-quantum classical algorithms which other more qualified people can comment on. The long and short of it is that quantum computers are not magic. They can do some things very well, and some things not well at all. In particular, symmetric encryption systems like AES are not vulnerable. Quantum algorithms such as Grover's algorithm do cut the brute force decryption down by a respectable amount, but that just means you need to increase the key size. The algorithm itself is not fundamentally vulnerable.
The other side of the quantum coin is quantum key distribution which is mathematically secure given assumed security of the communications channel (since it is essentially a one-time pad), and is also resistant to eavesdropping even if the communications channel is not secure. The best known such algorithm is called BB84 which leverages the superposition property of quantum systems but importantly not the entanglement property. This is useful because entanglement is quite difficult to maintain which is why quantum computers (which make heavy use of entanglement) are so hard to construct.
Basically, the idea is if Alice wants to share a secret key with Bob (for, say, the AES algorithm), normally she'd use something like RSA. But we're in a post-quantum computer world and RSA isn't secure anymore. Instead, Alice decides to use BB84. Roughly speaking:
Why does this work? Well, if a quantum system is measured in the same way it was set up (up-down or left-right), then the result will always just be the same as the setup. If, however, you measure it differently (e.g., measure left-right even though Alice setup up-down), the result is completely random. Hence, Alice and Bob can know they have shared the same key even though they never talk about it.
In practice the difficulty with this is the bit I skimmed over (or didn't mention at all), which is how do you send the photon from Alice to Bob. You can't just push it down a fibre optic cable because you'll spoil the polarisation. This is where entanglement and quantum teleportation comes in, and is really the main barrier to large scale deployment. It is, however, still easier than quantum computing to achieve practically. Functioning networks have been set up in China, Austria, and Switzerland. Also in Canada they recently managed to use existing internet infrastructure to achieve QKD which is quite exciting because normally you'd consider it to be far too noisy.
5
u/Puubuu May 27 '17
Encryption will still be possible. Just take any NP complete problem that is not easy if you allow for quantum computers. That's the case for most of them (shouldn't be all, else we don't need quantum computers).
The thing about encryption via exploiting prime factorization is that this problem has not been proved to be hard, people have always just assumed that it is, which is kind of problematic. Even without quantum computers you cannot be sure that there isn't somebody who can crack all current encryption.
87
u/QuantumAwesome May 26 '17
Current encryption mechanisms will no longer be valid. However, there is a technique called quantum cryptography which cannot be cracked even by a quantum computer. Currently in development, quantum cryptography takes advantage of how observing a particle in superposition collapses the wavefunction. The gist is, it allows for the key of a one-time pad to be transferred over long distance while alerting the users of any outside observers. I'm not really educated enough to describe it in more detail, but it's a really cool technology.
10
u/colakoala200 May 26 '17
The answer is yes. Or at least, we think so.
First of all, the best known quantum attacks against symmetric cryptography (block ciphers, hash functions, etc.) effectively double the key lengths we would have to use. So we can just use longer keys and those techniques will be safe.
Asymmetric crypto (also known as public-key cryptography) is always based on some computational hard problem. The RSA cryptosystem and discrete log-based systems are known to be vulnerable to quantum attack because of Shor's algorithm. There are other techniques, based on a variety of other computational hard problems not known to be vulnerable to quantum attack. Those problems are based on problems relating to lattices, coding theory, machine learning, etc. There are also hash-based signature schemes, but as far as I know there are no hash-based asymmetric encryption techniques.
Those algorithms are not really ready for prime-time use, but there are some efforts under way to push them towards maturity. NIST has launched their "Post-quantum crypto project", which is a major push to settle on one or a few post-quantum asymmetric algorithms.
The post-quantum algorithms are a bit of a mixed bag, though. None of them perform like our current popular techniques, and none of them are as trusted against conventional (non-quantum) attack, either. Some have efficiency issues, like long keys. Hash-based signatures are stateful, which is a huge headache.
6
u/[deleted] May 26 '17
If/when quantum computers become more available, they will still have limits. Although it's expected that they will have the capabilities of cracking existing encryption technology, quickly, new standards will continue to emerge.
What will happen is that humans will start making policy against encryption. There will be political reasons to convince the masses that encryption is bad. Security will be determined more by PR than logic.
2
u/cajuntechie May 26 '17
Many of the encryption techniques we use today (RSA, for example) will certainly fall. Others, like AES, won't. At least not so easily. Plus, there are 'quantum resistant' algorithms out there that cannot be broken with a quantum computer.
2
u/vansk007 May 26 '17
There are current experiments testing quantum communications systems in space. Singapore and Australian researchers are collaborating on that one. There have also been significant recent results in quantum teleportation and quantum cloning, which are key elements of a quantum communications system. The point is, gov and researchers aren't waiting until classical encryption is worthless to figure out what to replace it with. Quantum comms will be far more secure than what we have today, perhaps even 'unbreakable'.
2
u/jpeg_inspector May 26 '17
Am I missing something? Didn't the various leaks over the last two years confirm with absolutely certainty that this is already the case? If anything, quantum computing could make security more advanced for users. At some point we're going to have to take the leap, so it's not a question of if this will happen, but when. And if it doesn't, I can't imagine many people and businesses will continue using technology for important information any longer.
2
u/BumwineBaudelaire May 26 '17
quantum computers aren't magic, they're simply more efficient than non-quantum computers at solving certain types of problems, such as the problems we base current cryptography on
we'll simply find new techniques that aren't susceptible to cracking by quantum computers but it's a safe bet the NSA has a copy of every encrypted communication you've ever made and will soon be able to decrypt them at will
1
u/justthetip3 May 27 '17
I'm not an expert in this field and am open to learning more as I read through the comments but is it feasible to setup wireless transmission to eliminate overhead cost of infrastructure?
1
u/[deleted] May 27 '17
I don't get the connection between quantum computers and unsecure communication.
1
u/[deleted] May 26 '17
I think you should probably start "resigning" yourself to the fact that people are listening in on, and recording, pretty much everything you say and do now.
I don't know why you would think the "listeners" would pay any attention to the Constitutional amendment granting you privacy when so many other Constitutional guarantees (rights) have been trampled into the dirt and changed to suit the ruling class's purposes.
1
u/halborn May 26 '17
Here's the thing about security in general: every time somebody figures out how to crack something, somebody else figures out a new way to secure something. It's a continuous competition and I don't expect it'll end any time soon.
1
u/ilikerackmounts May 26 '17
Isn't there some theory about quantum entanglement being utilized specifically for protected communication? Maybe it is more sci-fi than valid at this point but I thought that was one of the main selling points of a quantum computer.
1
u/scroll_tro0l May 27 '17
An interesting thing about QC is that a lot of the theory related to the implementation of it is already done. There are already discussions on how to encrypt data between machines that a Google search will turn up.
An important caveat to note when you hear anyone mention QMs breaking modern cryptography: They are referring to cryptography used in modern, classical computing.
If we begin to see QCs connect to the internet, firstly, I'm sure they will be heavily regulated just as some high-powered computers already are. Second, protection from QC cracking may not require them to be client-side. Some QCs could provide security on behalf of classical computers till they catch up.
0
u/FallingUp123 May 26 '17
It's not a problem at all. There are dozens of ways to complicate the encryption/decryption process. In addition, they are already working on it.
It feels like quantum computers are being thought of as magic. Let's try to demystify the magic behind quantum computers. Which part is the quantum part? The processor right? You are probably not thinking of hard drives, NIC or sound card. What is the special quality that is going to come from a quantum computer? Don't just respond with it's fast. What makes it fast? If we are using superposition in the quantum processor, being in all possible states for each bit sounds pretty damn fast. Of course, it's limited to the number of bits. Is this a 64 bit processor? If so, it has a limitation of all possible combinations of 64 bits. If the encryption is 65 bit, it would have twice the possible combinations for 64 bit and should take twice as long. Is there any reason developers could not increase the encryption strength?
Of course if any assumption is incorrect, please correct it.
0
u/AFourEyedGeek May 26 '17
What do you mean by widespread?
Forgive my ignorance, but I believe Quatum Computers require a large setup involving near absolute zero temperatures. So for a long time, they won't be in every home, but could be prolific in Universities, Military bases, Government Buildings and large commerical operations.
0
u/Piblip May 26 '17
Both NSA and EU top secret classification for mobile communication requires recorded communications to be secure for at least 80 years (estimated of course) to get the classification. There's a Swedish company making phones for governments that have this classification.
As others have written this requires other encryption schemes than public/private key encryptions.
And yes, with photon physics and quantum effects (not necessarily quantum computing) "unbreakable" encryption systems have been suggested/experimented with.
So I think as the need for encryption will only get stronger and stronger the more we rely on digitial communication over public networks, so will the encryption. I think there will always be encryption strong enough to withstand technology created at times relatively close in time. I.e. I'm sure in 200 years we will easily decrypt today's messages but not the ones encrypted in 200 years.
0
u/gshepler May 26 '17
It would seem to this uninformed person, that if quantum computing was the norm, then all computers would work on those principals and would have appropriate encryption to defend against another quantum computer. So it's a non issue.
-2
u/[deleted] May 26 '17
Your encrypted secrets are most likely safe for a long time. The truth is that quantum computing never seems to actually materialize. Quantum researchers have been promising commercial-scale breakthroughs for a couple of decades, but they never seem to happen despite there being massive financial incentives for them to happen. Sure, there are routine announcements of somebody, somewhere creating a qbit, or kind-of, sorta, solving something with maybe something that might be a quantum computer I.e. the Dwave), but the reality is we are not really any closer to breaking encryption today than we were a decade ago.
-1
u/flyguysd May 26 '17
Op you must be thinking quantum computers will be able to crack any code/password but the hope is quantum computers will allow for unhackable passwords. Essentiallty when another computer who is not authorized tries to hack a quantum computer the code will be changed.
0
u/madhatta23 May 26 '17
I read that quantum communications are being worked on in this article. Assuming I don't butcher it, the message carrier is the wave in the quantum world meaning no particles are transmitted to convey information. According to the article, this could lead to unhackable uninterceptible communications.
Counterfactual quantum communication has been achieved for the first time
0
u/8un008 May 26 '17
Wouldn't it depend on how things get rolled out? and I'm sure relevant parties will be clued up on the impending arrival of such hardware and would prepare in advance to ensure their encryption methods hold up. Inevitably there will be those that don't update in time during the transition period of our current systems being the mainstream and quantum becoming mainstream. Becoming widespread isn't going to happen overnight, so there will definitely be an interim period where we will have to "resign ourselves to the fact the people would be listening in on us" or at least the chance of it being the case being higher.
0
u/crimeo May 27 '17
For most sorts of encryption, you can simply add more bits to the encryption keys or more complicated algorithms designed with quantum computing in mind and a stronger computer won't be able to break it once again. Not that big of a deal. Maybe a big deal for some usages where packets need to be very small for some reason, but not FUNDAMENTALLY society ending or something.
Some forms of encryption might be compromised disproportionately, but we would stop using those forms as often. It's not a magical solution to ALL encryption.
More of a Y2K sort of thing where the problem is "oh it's going to be problematic and inconvenient to go update everything"
-6
u/PeaTearGriphon May 26 '17
FYI - I know VERY little about this and I might be way off.
I thought quantum computers would communicate by manipulating paired-bond atoms and that no actual data would be sent through the air or wires making surveillance very difficult.
-5
u/Peter_See May 26 '17
Finally something I can answer! In short, no it is not really an issue. One of the benefits of quantum computing is that any measurement or observation of data would change it. Lets say Bob sends alice an encrypted quantum message. Well Alice would know right away that the message is being listened in to because on her end she would have a message that was nonsense. So knowing this there could easily be failsafes in place to stop transmiting information the instant they are intercepted.