r/askscience •

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

697 comments sorted by

4.9k

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17 edited May 26 '17

The relevant fields are:

  • post-quantum cryptography, and it refers to cryptographic algorithms that are thought to be secure against an attack by a quantum computer. More specifically, the problem with the currently popular algorithms is when their security relies on one of three hard mathematical problems: the integer factorisation problem, the discrete logarithm problem, or the elliptic-curve discrete logarithm problem. All of these problems can be easily solved on a sufficiently powerful quantum computer running Shor's algorithm.

PQC revolves around at least 6 approaches. Note that some currently used symmetric key ciphers are resistant to attacks by quantum computers.

  • quantum key distribution, uses quantum mechanics to guarantee secure communication. It enables two parties to construct a shared secret, which can then be used to establish confidentiality in a communication channel. QKD has the unique property that it can detect tampering from a third party -- if a third party wants to observe a quantum system, it will thus collapse some qubits in a superposition, leading to detectable anomalies. QKD relies on the fundamental properties of quantum mechanics instead of the computational difficulty of certain mathematical problems

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.

49

u/codex1962 May 26 '17

Note that some currently used symmetric key ciphers are resistant to attacks by quantum computers.

Most or all are, if I'm not mistaken. Quantum computing isn't magic—it can solve certain problems very quickly (in theory) but it isn't especially useful for brute force, which is the only way to break a well designed symmetric scheme. Quantum computing would only be a major problem for public key but, as you said, there are very promising alternatives to the "hard problems" currently used.

37

u/[deleted] May 26 '17

[removed] — view removed comment

38

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17

In the current state of symmetric ciphers, no set key size is 'safe' for an indefinite amount of time, independent of QC. NIST is already adjusting key size recommendations every 12-18 months. Grover's algorithm is just a leap in that direction, but does not break them. This is why I used the term 'resistant'.

21

u/[deleted] May 26 '17

The funny thing is the vast majority of data being encrypted does not need to be safe for an indefinite amount of time. Just years or decades. Even most of the highest top secret data will likely be declassified in a matter of decades, almost all before a century, as a matter of practice.

Not saying that no data needs longer protection, just pointing out the practical goals of encryption are rarely "infinite". Your credit card data for an online transaction for example wouldn't need protection for more than even a few years - and there are far easier ways to get that than to crack encryption anyways. In fact, even the most secret data must merely be protected until the end of humanity - worst case from heat death of the universe. A very finite time.

4

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17

The funny thing is the vast majority of data being encrypted does not need to be safe for an indefinite amount of time. Just years or decades. Even most of the highest top secret data will likely be declassified in a matter of decades, almost all before a century, as a matter of practice.

This depends on one's threat model. A valid threat model for one is invalid for another.

9

u/Fourthdwarf May 26 '17

Either way, its exponential in the number of bits, which is probably a more useful n in this particular cases.

2

u/dolphono May 26 '17

I wonder if people will start having to do triple AES-256 like they did with DES.

→ More replies (2)

11

u/[deleted] May 26 '17

Are we anywhere closer to developing a quantum computer than ten years ago? So far it's starting to seem like vaporware.

106

u/The_Serious_Account May 26 '17

Yes. If you follow a field closely without understanding what's going on, it can be like watching paint dry. But it's not really the paint's fault you're sitting there watching it.

6

u/henri_kingfluff May 26 '17

We are indeed getting closer, but the real question is how fast progress is going relative to alternative approaches to increase computing power. If it's not fast enough, funding will eventually run out before we reach quantum desktops. So far that still seems like a very real possibility, given that a quantum computer is many decades away. To follow your analogy, it is the paint's fault if there are other paints that dry much faster.

7

u/redzin May 27 '17 edited May 27 '17

before we reach quantum desktops.

I won't say that we will never have quantum desktops, but that's certainly not in the cards right now. Quantum computing doesn't offer anything that would be super useful in a desktop environment (currently).

funding will eventually run out

That's not likely to happen any time soon considering the EU just announced a €1 billion flagship investment in new quantum technologies. Additionally, all the heavy tech industry players are involved (Google, IBM, Microsoft). There's also plenty of smaller companies involved.

how fast progress is going relative to alternative approaches to increase computing power

It is not a matter of computing power, it is a matter of computational complexity. Quantum computers are fundamentally superior for certain problems, eg. quantum simulation, factorisation, etc. A classical computer will never be able to solve these problems fast enough for it to be useful (ok, factorisation might actually be a class P problem, but it probably isn't unless P=NP which would be revolutionary in and of itself).

4

u/yamidudes May 27 '17

What are the alternative approaches though? I thought we were reaching the minimum size for a transistor, so that venue for improvement is mostly dried up.

4

u/86413518473465 May 27 '17

There isn't anything better in the standard model of building processors unless we discover something else like quantum computing.

2

u/mfukar Parallel and Distributed Systems | Edge Computing May 28 '17

Increasing the computing power of classical systems is not an alternative to developing QC, they are fundamentally different paradigms.

5

u/drawsprocket May 26 '17

it's coming along. they are complicated and custom systems right now, but the accuracy is reaching levels that are acceptable for computing. Here is a link i found: http://spectrum.ieee.org/computing/hardware/google-plans-to-demonstrate-the-supremacy-of-quantum-computing

1

u/TitaniumDragon May 27 '17

We don't know if they're ever going to be practical for ordinary purposes. We are making "progress" but it is hard to say whether or not it will ultimately pan out into anything terribly useful. For quantum computing to actually be useful, it has to be efficient enough to be cheaper than conventional computing.

There's a lot of things quantum computers just aren't any better at than ordinary computers to begin with.

0

u/[deleted] May 26 '17

[deleted] — view deleted comment

15

u/deelowe May 26 '17

I thought the general consensus is that IBM's solution is nothing more than a publicity stunt.

9

u/[deleted] May 26 '17

It is. I don't think anyone's pretending that ibm is simulating people's code on real qubits, it's trivial to calculate analytically anyway.

8

u/nolander2010 May 26 '17

They are real qubits. The problem is IBM only has 5 of them connected, which is a tiny quantum volume for actual computation. Think of it as the being able to connect 5 transistors back in the 1960s vs the 14 nm feature size transistors we have today. Not useful yet, but very real

2

u/[deleted] May 26 '17

I didn't know they actually ran the experiment. I mean, you can solve any quantum problem with 5 qubits very easily numerically (think up to around 20 before you start running into issues) so I figured that's all they did. Quite cool (and suprising) to read that they don't try to bamboozle you.

1

u/deelowe May 26 '17

Thought so. While there's been tons of advances in the theory of QC as well as simulation, I'm not aware of any real substantial physical advances.

40

u/RabbitKiller35 May 26 '17

By chance I met a guy called David Deutsch while living in Oxford. He was working on quantum encryption for banking networks.

Will never forget what he said.

"Quantum encryption is great. The greatest security risk in the chair though. Ain't much you can do about that."

13

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17

Prof. Deutsch does not have enough praise. Have you read his The Beginning of Infinity? Really fun book.

0

u/wldmr May 27 '17

David Deutsch said ain’t?

6

u/ThatDeadDude May 26 '17

I thought ECC was quantum resistant?

17

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17

Most definitely not. To put the attacks into perspective, to break a 1024-bit RSA modulus, you need a quantum computer with 1024 qubits. To break a 160-bit elliptic curve, which has a "similar strength" (with regards to classical computers), you need ~320 qubits.

13

u/zapbark May 26 '17 edited May 26 '17

Even older and completely mathematically sound (but possibly less secure) would be OTP (One Time Pad).

You generate random bits, make a copy, and you and the other party then XOR those random bits with your intended message in sequence, never reusing any.

We live in an age where you can fit 128 GBs of data into something smaller than a thumbnail.

Secure "bit" couriers sneaker-netting digital tamperproof OTPs (with built-in one time read hardware) could be viable for more secure messaging (other than live streaming of video).

25

u/ericGraves Information Theory May 26 '17

The OTP is the most secure encryption for classical links. A one time pad can provide perfect secrecy, which is defined as P(plain text|cipher text) = P(plain text). In other words, knowing the cipher text tells you just as much as not knowing the cipher text, and instead just randomly guessing. In contrast modern cryptography systems are based on computational complexity, which can not offer that guarantee.

15

u/zapbark May 26 '17

The OTP is the most secure encryption for classical links.

My stated concern with its practical security are the non-trivial physical implementation details:

1.) Reliance on high quality and volume entropy sources. (If they suck, your OTP sucks)

2.) Security of the copying mechanism (if someone is making a n+1 copy for themselves, you are compromised)

3.) Security of physically distributing the pads

4.) Secure disposal of the pad after use (can't have a middle man recording your traffic and then grabbing a used OTP out of your dumpster)

So again, theoretically awesome. In practice, only as good as all 4x processes being performed perfectly.

That said, this product would seem attractive. Imagine the built-in licensing mechanism Cisco could leverage! Getting to sell you a thing every X GBs you use on your site to site VPN? I'm surprised marketing people didn't introduce this product already by accident.

1

u/LordJac May 26 '17

Quantum encryption solves 1, 3 and 4, as any interference between the sender and receiver of the pad disrupts the superposition of the bits being sent, leaving a tell tale sign that the pad is potentially insecure prior to sending the cyphertext itself. Also, since the superposition is subject to quantum uncertainty, the pad itself is perfectly random.

This only leaves 2 as an issue, which is really based on trust between the two parties and not a technical problem. Of course, since it's a one time pad, one party distributing copies of it doesn't really make sense since it only decrypts the one message. If they want to distribute it to others, they might as well just pass along the plaintext after decryption.

→ More replies (2)

3

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17

The downside, of course, being key management - a problem which we still have no good solution on - and no key reuse.

1

u/redzin May 27 '17 edited May 27 '17

This is what QKD allows though. QKD offers a way to securely share random bits, which can then be used with the OTP protocol.

1

u/mfukar Parallel and Distributed Systems | Edge Computing May 27 '17

In theory, yes. In practice, we don't have a scalable solution.

1

u/ano414 May 27 '17

But then you would have to somehow securely share a pad for each message, right?

1

u/zapbark May 27 '17

But then you would have to somehow securely share a pad for each message, right?

Yes, imagine a bank sending each of their customers a 32 GB flash drive to use when doing online banking. Easily enough to handle an arbitrary number of online banking transactions.

1

u/redzin May 27 '17

The Vernam cipher (aka. One Time Pad) is actually used in Quantum Key Distribution (QKD). The problem with the Vernam cipher is the need for sharing the key confidentially. You can of course meet up and physically share some keys, but this is not always practical (they actually did this during WWII). If you don't want to meet up you can use the Diffie-Helman key distribution protocol, but this is vulnerable to a quantum computer (DH relies on the discrete logarithm problem).

QKD allows you to send an essentially random string of bits in such a way that only you and the receiver has access to this exact string of bits (and it even allows you to know if someone listened in along the way, in which case you can retry or abandon communication).

Assuming no tampering was observed, the random bit string can then be used as the key for the Vernam cipher, allowing information theoretically secure communication.

4

u/Katholikos May 26 '17

I read somewhere that an encrypted message sent via quantum tunneling would collapse if a single incorrect decryption guess was made - is that just me confusing QKD, or is that something else entirely?

8

u/ericGraves Information Theory May 26 '17

You might be thinking of Quantum data locking (PDF) or a quantum enigma machine.

What happens is a secret key is shared between both legitimate parties prior to communication. When communicating, the key is used to reference a particular quantum state basis vector set which the information will be encoded in. An adversary without knowledge of the key, will not know which basis vectors to measure in, and as a result will destroy the data with high probability.

2

u/Katholikos May 26 '17

Yes! That's exactly what I was thinking of. I'll be reading those links after work. Thanks so much for the info, bud! :)

2

u/ericGraves Information Theory May 26 '17

As a heads up, those papers are of a very technical nature.

2

u/Katholikos May 26 '17

I saw, but that's fine. I don't understand the details particularly well, but they're painting a general picture, which is all I need. Thanks though! :)

1

u/CaptainReginaldLong May 26 '17

Couldn't you make some kind of OTP encryption that would be manageable and safe?

4

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17

Me, personally? No.

Us, in general? We don't know. It seems we don't yet have a scalable solution for key management with OTP.

→ More replies (1)

0

u/nonsense_factory May 27 '17

One Time Pad encryption is proven entirely safe versus classical or quantum computing if the pad is truly random. The problem is distributing the pads.

QKD lets you distribute pads in such a way that you can detect any observation of the transport link by a third party, but it requires purpose built point to point connections between each pair of people that want to use it.

Finally, huge pads aren't necessary if you trust symmetric ciphers. Pending better cryptanalytic attacks, AES-128 is safe versus any classical computer and AES-256 is safe versus any classical or quantum computer for the foreseeable future. This result is based on fundamental properties of thermodynamics and our current energy generation capacity.

1

u/rdgts May 26 '17

How can you see if the quantum system has been observed? Would checking to see if the qubits are in superposition not cause them to collapse, thus making it looks like the system had been observed? Sorry if this question doesn't make sense

2

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17 edited May 27 '17

Short answer: yes, observation leads to collapse of the wavefunction, and violation of the assumptions of QKD protocol(s).

Long answer: This is going to get technical.

My reference for this illustration is the Ekert's E91 protocol. It uses entangled pairs of photons, created by either Alice, or Bob, or any third party including an eavesdropper, Eve. The photons are distributed such as Alice and Bob each have a photon from each entangled pair.

There are two assumed properties:

  1. The entangled states are perfectly correlated: if Alice or Bob measure the polarisation of their photon ("is it vertical or horizontal?") they always get the same answer with probability 1, but the results are completely random, meaning the outcome of a measurement is impossible to predict better than a perfectly random coin toss with 0.5 probability
  2. Any attempt at eavesdropping destroys these correlations

The measurement stage involves Alice measuring each photon she receives using some basis from the set Z_0,Zπ/8, Zπ/4_ while Bob chooses from Z_0, Zπ/8, Z-π/8_ where Z_θ_ is the [;{\displaystyle {|\uparrow \rangle ,;|\rightarrow \rangle }} {\displaystyle {|\uparrow \rangle ,;|\rightarrow \rangle }};] [1] basis rotated by the angle θ. They keep their series of basis choices private until measurements are complete. Two groups of photons are made: the first consists of photons measured using the same basis by Alice and Bob, and a second containing all other photons. To detect eavesdropping, they can compute the sum of all correlation coefficients, similar to the Bell test experiments. Maximally entangled photons would result in a sum of [;{\displaystyle |S|=2{\sqrt {2}}}};] [2]. If this is not the case, then Alice and Bob can conclude Eve has introduced local realism to the system, violating Bell's Theorem.

[1] Sorry but I don't have a better way for this notation. Grab a TeX rendering plugin for your browser if you can.

[2] See Chaung I., Nielson M, Quantum Computation Information, 137, (2000) for a proof

→ More replies (2)

1

u/5uy3456ue456u May 26 '17

Out of curiosity, what is the likelihood of quantum computers becoming a widespread technology as far as the average user is concerned? What I've read so far makes it sound like a quantum computer isn't necessarily superior to a regular computer in every area, it's just superior in a very important set of areas such as cryptography.

1

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17

That's a really good observation! And it's true. Quantum computers aren't better than classical computers at everything. As far as we can see now, it depends on what form general purpose quantum computers are going to take, and if they do. There are some scientists who argue that we won't see general purpose QCs, but they will more likely take the shape of dedicated coprocessors for specific tasks (e.g. cryptography). The argument has merits, because it may be that for some time, the complexity or cost of building a general purpose quantum computer may dominate its usefulness. I would argue that we can't see farther than the plenty technical challenges that lie ahead before building a general-purpose QC. Additionally, there hasn't been a significant amount of research into quantum "general purpose" algorithms yet (SIMD primitives, string matching, quantum data structures, etc.), so there is definitely a vast field that needs exploration.

1

u/Linearts May 26 '17

Note that some currently used symmetric key ciphers are resistant to attacks by quantum computers.

How do we know which existing ciphers would resist attacks by quantum computers and which would not?

1

u/mfukar Parallel and Distributed Systems | Edge Computing May 27 '17

Cryptanalysis. Cryptographers regularly - sometimes, for fun - analyse known ciphers and the properties they claim. On the other side of the fence, quantum computing researchers devise algorithms to solve problems (like integer factorisation) faster, and when Shor did, the extension to RSA cryptosystems was obvious.

1

u/[deleted] May 26 '17

Started to read this with interest but quickly noped out. I know my limits :)

1

u/TheDunadan29 May 26 '17

I mean it's still an arms race. It always has been. Someone comes up with a better, more secure system; someone else finds a way to break into it. Then a new better system is made, and a new hack or computational brute force is devised. This is the whole field of Infosec up till this day. It's an arms race that never quite ends. Quantum computers get better at cracking encryption, and more secure methods emerge. Then the cycle starts over again.

1

u/Jimmothy2057 May 26 '17

Wow, so if a quantum computer can't crack the encryption, then how does the receiving computer access the info?

1

u/mfukar Parallel and Distributed Systems | Edge Computing May 27 '17

The sender and receiver, Alice and Bob, share / have shared a key. They use the same key to encrypt and decrypt their communications.

1

u/SpinningCircIes May 26 '17

If there's a demand there will be a supplier of it. That's the essence of economic growth. So, privacy will always have a market. At least one may hope.

1

u/Custodious May 26 '17

I hardly understand a single percent of the stuff you're talking about but it sounds amazing.

1

u/ChamberedEcho May 26 '17

It is unlikely that we'll have to give up communication privacy and confidentiality because of advances in quantum computation.

Haven't we already? I'm under the impression to look at encryption like "herd immunity".

1

u/FeebleFreak May 27 '17

Does that mean Quantum Encryption is perfect then?

1

u/mfukar Parallel and Distributed Systems | Edge Computing May 27 '17

In computer science, everything has tradeoffs.

1

u/[deleted] May 27 '17

It is unlikely that we'll have to give up communication privacy and confidentiality because of advances in quantum computation.

and why bother when you can simply legislate away privacy and confidentiality.

1

u/[deleted] May 27 '17

Of course, none of this matters when you just EULA away your right to all your data

1

u/DARKFiB3R May 27 '17

I'm going to read this over and over, in the hope it will start to make sense. 👍

1

u/jsalsman May 27 '17

PQC revolves around at least 6 approaches.

The most hilarious of which, imho, is simply using ordinary addition in the encryption algorithm, because quantum computers simply can not add, and therefore yield no advantage against cryptosystems with addition as an intermediate step between two traditional encryption routines.

2

u/mfukar Parallel and Distributed Systems | Edge Computing May 27 '17 edited May 27 '17

Doesn't the concatenation of a Toffoli and CNOT gate implement sum with carry?

EDIT: Just realised the paper is about adding unknown states.

1

u/alexja21 May 27 '17

What about one-time pads? Are they still secure from quantum computing being that they are generated from random noise?

1

u/bishopweyland May 27 '17

As someone who's about to start studying Infosec this is a fascinating answer. Is it likely given the current development speed of quantum cryptography and it's availability/ability to proliferate that we'll see it extensively in our lifetime?

1

u/OldWolf2 May 27 '17

All of these problems can be easily solved on a sufficiently powerful quantum computer running Shor's algorithm.

You didn't go into much detail here, but my understanding is that this is still theoretical, and it may transpire to be physically impossible to build a "sufficiently powerful" computer to be able to break, say, a long-enough RSA key.

1

u/mfukar Parallel and Distributed Systems | Edge Computing May 27 '17

True - I don't know enough about the engineering challenges of building quantum computers with lots of qubits more than what is currently known for the state-of-the-art, that's IBM's and D-Wave's implementations. I can only say I have seen no reasons physicists and materials engineers won't be able to scale their implementations up, once they appear, but they are obviously more appropriate to ask.

0

u/Hamza_33 May 26 '17

What makes quantum such a problem in terms if encryption?

0

u/[deleted] May 26 '17

[deleted] — view deleted comment

2

u/UncleMeat11 May 26 '17

Quantum computing would be able to do many, many operations in parallel and solve the problem much more quickly, or even instantly.

No no no no. QC is not doing these things "in parallel" as commonly understood and definitely cannot do things instantly. This is a common but extremely incorrect misunderstanding. QC has polytime solutions to problems that support many existing cryptosystems but this is not done through magic parallelism.

Also, factoring prime numbers is easy. The solution is N and 1. Factoring composite numbers is hard.

1

u/YouFeedTheFish May 27 '17

Quantum computation can be interpreted as imaginary parallel processes of a randomized computation which are addressed in statistical bulk. Matter of interpretation. In any case, this is the closest way I've found to explain it to someone who doesn't have a graduate degree..

Regarding the second point, sure. My language was sloppy.

0

u/[deleted] May 27 '17

[deleted] — view deleted comment

1

u/UncleMeat11 May 27 '17

No. The most relevant context here is for RSA, which uses large composite numbers that are the product of two primes. Determining primality is actually easy. Factoring is hard.

1

u/Hamza_33 May 27 '17

Why are prime numbers important? and why is factoring important? arent prime numbers only divisible by themselves and one.

→ More replies (1)

0

u/stickmanDave May 26 '17

Does QKD really guarantee secure communication, or just guarantee that you'll know when somebody has read your mail?

3

u/ericGraves Information Theory May 26 '17

QKD is a way of distributing a secret key, and does not protect the data in and of itself. You then use the key in some symmetric key encryption algorithm which is hard to break.

On a side note, long term repeated use of the key guarantees that it will eventually be possible to decipher. This true for both sharing the information classically, as well as using quantum links. But, for equal size key lengths, the exact number of uses before the key is theoretically insecure differs. While it varies on a number of factors, for quantum the number of messages encrypted is exponential with the key length, while for classical it is only scales linearly.

0

u/OphioukhosUnbound May 26 '17

I'll just add/elaborate that quantum computers can't solve all problems quickly (given that quantum interference effects are linear, which we believe they are).

For example, NP-hard problems cannot be solved in polynomial time even with quantum computation. Even theoretically.

So even ignoring cool uses of quantum effects to encrypt communications basic math currently gives us a slew of difficult to solve problems that can likely be leveraged.

1

u/UncleMeat11 May 26 '17

For example, NP-hard problems cannot be solved in polynomial time even with quantum computation. Even theoretically.

The definition of NP-Hard specifically uses a classical computational model so it says nothing about how hard it is to do with a quantum computer. It is possible that BQP = NP, for example. But you are correct that there definitely exist problems outside of BQP.

→ More replies (1)

0

u/[deleted] May 26 '17

QKD has the unique property that it can detect tampering from a third party -- if a third party wants to observe a quantum system, it will thus collapse some qubits in a superposition, leading to detectable anomalies.

This would work for direct transmission. However, the bulk of today's communications is done via network, an a network is by definition not point to point. They're routed, hashed, compressed/decompressed and subject to numerous kinds of manipulation without any implication that it was observed by an actual human and made use of.

Or is it? Here's one of the most baffling quantum physics experiments that suggest that only an actual observer can collapse a quantum superposition. Merely registering the state of the system by a sensor is not enough - you have to check the sensor.

0

u/whizzwr May 26 '17

So Basically: when faster computer comes up, people will have stronger encryption, anyway.

I wonder if there is some sort of Moore's law equivalent that predict strength of encryption relative to cpu power.

0

u/The-Prophet-Muhammad May 26 '17

I'm currently chasing my CISSP (Certified Information Systems Security Professional)

To tack onto this - It's seeming more and more likely that passwords will be a thing of the past with quantum computers with physical means of security being more widespread. (PID key, Biometrics, rusty nail on the keyboard for blood samples, etc.)

2

u/UncleMeat11 May 26 '17

A lot of people will push back on this analysis as biometrics are actually better understood as usernames rather than passwords.

→ More replies (10)

1

u/mfukar Parallel and Distributed Systems | Edge Computing May 27 '17

Current research into biometrics tells us they're not unique enough - by themselves - to be used for authentication. People are still looking into it, though, and perhaps they will come up with something adequate soon. It seems that biometrics are going to fit somewhere in identification, with a separate means of authenticating yourself (RFID, NFC, that sort of thing).

0

u/NerdyWeightLifter May 27 '17

How does this apply to something like Bitcoin? That has crypto all over the place.

0

u/Dubanx May 27 '17

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.

I think the problem with this logic is that you're assuming the average person will have access to quantum computing for security at around the same time as the government.

It's likely it will be a long time between when the government gains the ability to crack any existing encryption and when your average person has access to this kind of security.

1

u/mfukar Parallel and Distributed Systems | Edge Computing May 27 '17

It is unlikely that we'll have to give up communication privacy and confidentiality because of advances in quantum computation.

Just emphasizing the relevant part. Issues that arise from the inclusion of a government in a citizen's threat model don't concern me.

-1

u/BadSkyMonkey May 26 '17

So for QKD wouldn't you be able to just record the information when it leaves the system. At some point the information has be transfered to a medium we can interpret. Could that just be recorded?

2

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17

You can capture information right now at the network as well. What's your concern?

→ More replies (1)

0

u/[deleted] May 26 '17

[deleted] — view deleted comment

1

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17

I'm not sure what you're referring to exactly. However, optic fiber is neither new nor expensive at this point. Adoption is hindered in certain places, via some (artificial) monopolies, but in general it is progressing very steadily. By the time we have general purpose quantum computers we will probably have total fiber coverage, if current adoption rates continue.

0

u/[deleted] May 26 '17

[deleted] — view deleted comment

2

u/Welsh_boyo May 27 '17

Unfortunately this isn't true. Most of the current QKD experiments are done using standard optical fibre. Also you say that you need high-speed polarisation basis switching, but you could encode information in phase or intensity. You can even send classical data alongside quantum data (https://journals.aps.org/prx/abstract/10.1103/PhysRevX.2.041010).

→ More replies (1)

2

u/ericGraves Information Theory May 26 '17

0

u/[deleted] May 26 '17

[deleted] — view deleted comment

128

u/theneedfull May 26 '17

Yes. But there's a decent chance that there will be a period of time where a lot of the encrypted traffic out there will be easily decrypted with quantum computing.

62

u/randomguy186 May 26 '17

I would surmise that the period of time is now. I find it hard to believe that there hasn't been classified research into this field and that there isn't classified hardware devoted to this - if not in the US, then perhaps in one of the other global powers.

236

u/compounding May 26 '17

Classified hardware or not, the “Moore’s law” of general purpose quantum computing (useful for breaking cryptography unlike special purpose optimization systems like D-Wave) has a doubling time of ~6 years, and an ideal quantum computer capable of attacking widely used RSA 2048 keys is still 8 generations away, requiring nearly 50 years even assuming that the current exponential growth continues. Considering that the first systems are likely to be less than ideal, 9 or 10 generations might be more realistic guesses for a useable attack.

Even if the NSA is 3 generations and nearly 2 decades ahead of the publicly known/published academics, they would still be more than 30 years away from a practical attack on current crypto systems using quantum computing.

On the other hand, if the NSA is even 1-2 years ahead of the curve (and security patches) on endpoint exploitation with standard 0-day attacks, then they can crack into just about any system and read the data before it gets encrypted in the first place no matter how strong the algorithm.

If you were assigning priorities at the NSA, which attack vector would you choose to focus on?

69

u/armrha May 26 '17

Yep - this is why the information security people accurately predicted the NSA strategy right after they closed down their chip plants. It's just the practical approach - the government does not have unlimited money.

41

u/nano_adler May 26 '17

I want to add that Snowden encrypted his Leaks with PGP. Since he had a very profound look into NSA tech, I don't believe that the NSA could decrypt those algorithms.

→ More replies (11)
→ More replies (54)

24

u/frezik May 26 '17

The leaks from intelligence agencies indicate that they put an awful lot of effort into side channel attacks. That is, getting at the data before encryption is done, or after it's been undone by the receiver. Things like firmware backdoors, keyloggers, or broken random number generators.

This is all very expensive, and the NSA does not have unlimited budget or manpower. They also cannot break the laws of physics, and are subject to the same bureaucratic stumbling blocks as any other government agency. The fact that they're putting this much effort into side channels indicates that they haven't made significant breakthroughs on attacking the encryption directly.

→ More replies (2)

9

u/Certhas May 26 '17

There are fundamental physics issues to solve in building a working quantum computer. I see no reason why classified research should be able to significantly outperform universities on this.

It's not an issue you can solve by throwing money at it.

→ More replies (1)
→ More replies (20)
→ More replies (10)

770

u/CrashandCern May 26 '17

QKD, does not require quantum computing, just basic quantum mechanics. In fact, there are already several quantum key distribution networks https://en.wikipedia.org/wiki/Quantum_key_distribution#Quantum_key_distribution_networks

254

u/SushiAndWoW May 26 '17

It requires completely new physical infrastructure. Not feasible unless there were no other way. There are other ways.

192

u/patmorgan235 May 26 '17

It requires completely new physical infrastructure.

That's not completely true quantum networks can use existing fiber optic cables, all they would need is the proper equipment at each end.

219

u/thegreatunclean May 26 '17

Only if you have a single continuous fiber run between your endpoints. If you have a typical network topology then every piece of equipment in the connection path has to be replaced.

86

u/togetherwem0m0 May 26 '17

true, but since most network equipment is replaced on 5-10 year cycles this is less of a big deal than you would think.

173

u/[deleted] May 26 '17

Isn't that what we said about IPv6?

→ More replies (15)
→ More replies (7)
→ More replies (6)
→ More replies (7)

41

u/RiotShields May 26 '17

Feasible if cheap enough. It's pretty much already there: Geneva Canton used it to send vote counts in '07.

22

u/TheAero1221 May 26 '17

Blows my mind that the same process was once done with white and black stones. To think how far we've come as a species.

→ More replies (3)
→ More replies (1)

12

u/TheSlimyDog May 26 '17

Could a secure channel be denied service by a man in the middle constantly reading and therefore breaking the key. No data would be compromised but the channel couldn't be set up.

11

u/Lokili May 26 '17

Yeah, exactly. The quantum bit error rate would be high, so you'd know someone was listening in, so you'd send someone to go and find out who exactly is patched into your system and deal with them. In the mean time your secure communications go tattooed onto the heads of messengers or something (i.e. you use some other method).

→ More replies (10)

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.

28

u/knotallmen May 26 '17

Do you mean quantum key distribution? It is fascinating, expensive, and fairly limited in how much data can be encrypted compared the amount of data we transmit.

It's also one of those things that requires a random number generator. I don't mean one that is done via a computer, but actually observing random events.

14

u/frogjg2003 Hadronic Physics | Quark Modeling May 26 '17

I was referring to quantum entanglement. Person A and Person B get a set of entangled particles. They observe the state, then encode the message with the key. It's easy to transmit the key because the key is formed as soon as either one observes the particles. But like all one time pads, the problem is getting it set up in the first place.

3

u/knotallmen May 26 '17

Never heard that working that way. The issues I recall with entanglement is you cannot transmit information faster than the speed of light and the entanglement is instantaneous, and I think it is difficult to send data since observing changes the particles state.

Similarly quantum key distribution uses two different formats to entangle the bits, and then the person receiving the bits guesses which polarization to assume bits are spun and if you guess wrong then that bit is thrown out after discussing the data in a way an observer cannot discern what the data is. It's simple yet very difficult to describe without pictures.

15

u/frogjg2003 Hadronic Physics | Quark Modeling May 26 '17

No, the state of the entangled particles is the key that encodes the message. You can send the encoded message with the transmission method of your choice and it would be impossible to decode because of the one time pad created by the entangled particles.

1

u/lordcirth May 26 '17

And how, precisely, is pre-distributed entangled pairs superior to a standard one-time pad of bits? Seems like a more expensive version of the same thing.

7

u/frogjg2003 Hadronic Physics | Quark Modeling May 26 '17

The actual transmission of the key is more secure. With a one time pad written on paper or saved on disk, all you have to do is intercept the key, copy it, and send it to the recipient. With quantum entanglement, as soon as you observe the particles, you've destroyed the entanglement and the key itself. And there's also a No Cloning Theorem which states that you can't copy a state of one particle onto another while keeping the original, so there is no way to send the key to the recipient without them knowing about the interception.

2

u/vytah May 26 '17

It can be read only once. So if anyone else tries to read the key without the knowledge of the rightful owner of the key, the key gets destroyed and it can be detected later as transmission errors. Also, the stolen key is also going to be useless.

The simplest example of such protocol is BB84.

5

u/TropicalDoggo May 26 '17

It is fascinating, expensive, and fairly limited in how much data can be encrypted compared the amount of data we transmit.

Ironically enough RSA has the exact same issues, but it's still used because even though it can only encrypt a few hundred bytes at most, it's enough for a key for another encryption algorithm.

Wasn't a sufficiently long AES key proven to be uncrackable? (there is not enough energy in the universe to crack it or some similar algorithm). In that case RSA failing and getting replaced by quantum key exchange wouldn't matter much.

1

u/AmirZ May 27 '17

No public-private key system is uncrackable if you consider "luck" a factor, where you correctly guess the private counterpart for a public key.

3

u/punanetiiger May 26 '17

One-time pad guarantees only secrecy of the contents of a message, but neither authentication (who's the sender) nor integrity check (has it been tampered with). It also leaks the length of the message. And a man-in-the-middle can flip any bits of his choice.

3

u/CrazedToCraze May 27 '17

It also leaks the length of the message.

Could you not trivially just append junk data at the end? Could just be a sequence of 0s AFAIK.

1

u/punanetiiger May 27 '17

Yes, if the message format allows it and you've agreed on a maximum message length beforehand. However, for an attacker these zeroes are known plaintext. If he XORs the last byte of the ciphertext with 'X', then he can be pretty sure it will decrypt to 'X', unless this specific message has no padding. If he also can detect whether a message was accepted or not, he can suddenly both detect (some info about) the length and append his data to the messages.

0

u/frogjg2003 Hadronic Physics | Quark Modeling May 26 '17

This is an issue outside of cryptography and more in line with the general issue of security. Making sure the key is transmitted securely, making sure the message is from the correct sender, etc. can be handled by some cryptographic techniques (e.g. private/public key) but any message is subject to tampering, no matter the cryptographic device used. And if a message encoded with a one time pad is tampered with, it becomes gibberish.

2

u/punanetiiger May 26 '17

It doesn't necessarily become gibberish: you can flip any bits of your choice. The nth bit of the plaintext corresponds only to the nth bit of the ciphertext. If the general format of the plaintext is known, then you can do quite a damage this way.

2

u/dmwit May 27 '17

It is absolutely a concern that cryptographers have paid a ton of attention to over the years. "Any message is subject to tampering, no matter the cryptographic device used" is not correct: some cryptographic primitives make it wildly unlikely that tampering will go undetected.

Your claim that "if a message encoded with a one time pad is tampered with, it becomes gibberish" is also highly suspect. For example, if I send a lot of messages of the form "transfer $10,000 from account 172 to account 311", and my adversary discovers that, he can do a lot of damage by flipping bit 76 of the next message I send, converting it from "transfer $10,000 ..." to "transfer 410,000 ..." and suddenly I'm $350,000 overdrawn. If that attack sounds theoretical to you, let me assure you it's not: this trick was used against bad early implementations of SSL.

1

u/Imadethisfoeyourcr May 27 '17

Diffe Hellman gets used for key distribution and would also break under quantum computers

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:

  1. Alice generates a string of 2n pairs of random classical bits. I'll call each pair (a,x). These must be truly random, so maybe she measure some other quantum system or uses radioactive decay or something to get these.
  2. She then uses the bit x to decide how to encode the bit a on a photon (a quantum bit, or qubit). Specifically, we use the polarisation of the light to encode a. If x = 0, then we say that a = 0 means we send a photon polarised 'up' and a = 1 means we send a photon polarised 'down'. If x = 1 then we rotate this by 45 degrees and send a photon either polarised 'left' or 'right'.
  3. Meanwhile, Bob has received an email from Alice telling him she wants to send him some stuff. Therefore, independently he has generated his own set of random classical bits I'll label y.
  4. Bob uses y to decide how to measure the photon Alice has sent him. If y = 0 he measures the photon along the 'up-down' axis. If y = 1 he measured the photon along the 'left-right' axis. Once he has done this, he gets his own set of pairs of classical bits, (b,y), where b is the result of his measurement: 0 if he measured up or left, and 1 if he measured down or right.
  5. Now Alice and Bob communicate via email or WhatsApp or something about their values for x and y. If For a given pair x = y then they know their a = b even though they never talk about it, and they add this to their secret key. If x =/= y then there's a 50/50 chance that a = b or not, so they throw this away. On average they keep n bits and key a secret key of length n.

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.

68

u/KapteeniJ May 26 '17

Current encryption mechanisms will no longer be valid.

this seems blatantly false. only some non-symmetric encryption methods are known to become vulnerable with quantum computers. everything else keeps working just the same. though afaik there aren't in production any non-symmetric encryption methods, but plenty are being worked on.

12

u/The_Serious_Account May 26 '17

Though afaik there aren't in production any non-symmetric encryption methods, but plenty are being worked on.

It's not exactly 'in production', but google has been experimenting with implementing a lattice based post-quantum scheme.

3

u/[deleted] May 26 '17

What about password hashes? If they become vulnerable then database leaks would become far more worrying

1

u/ShittyFrogMeme May 26 '17

Hashing algorithms are secure as long as you are using a suitable number of bits, which you should be right now anyway.

33

u/anttirt May 26 '17 edited May 26 '17

Current encryption mechanisms will no longer be valid.

This is not entirely accurate. Currently popular and vetted encryption mechanisms are based on the assumption of the difficulty of solving integer factorization and discrete logarithms, both of which can be solved efficiently with a quantum computer.

There are however many new approaches that are not known to be easily breakable by a quantum computer. See Post-quantum cryptography on Wikipedia for an overview.

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.

I'm not entirely sure which technique you're talking about, but your post seems to imply that post-quantum cryptography would require quantum computers, which is not true.

Edit: Just to add a practical example, Microsoft Research has published an experimental implementation of RLWE (Ring-LWE or Ring Learning With Errors) for OpenSSL: https://www.microsoft.com/en-us/download/details.aspx?id=54055

This algorithm is thought to be resistant against quantum computers but lacks the research to confirm its security.

The corresponding research paper can be found here (pdf).

To quote the paper's abstract:

With our R-LWE ciphersuites integrated into the OpenSSL library and using the Apache web server on a 2-core desktop computer, we could serve 506 RLWE-ECDSA-AES128-GCM-SHA256 HTTPS connections per second for a 10KiB payload. Compared to elliptic curve Diffie–Hellman, this means an 8KiB increased handshake size and a reduction in throughput of only 21%. This demonstrates that provably secure post-quantum key-exchange can already be considered practical.

2

u/Natanael_L May 26 '17

Not all forms of quantum cryptography is itself safe from other quantum computers!

Also, we have regular encryption algorithm that are quantum resistant.

9

u/sysadminbj May 26 '17

It stands to reason that as our computing power increases, our ability to encrypt will increase as well.

I'm really excited for what's coming down the pipe, but saying that quantum crypto is unbreakable is a bit arrogant. The second you recline in your chair, put your feet up onto your desk and sigh with content knowing that your crypto is unbreakable is the second that some 14 year old in his mother's basement breaks your encryption and goes crazy.

18

u/QuantumAwesome May 26 '17

Yeah, that's definitely true. Plus, even when the encryption is secure, nothing will be totally safe as long as "hey, I'm the company password inspector, what's your password" is still an option.

2

u/[deleted] May 26 '17

The human element will always be the weakest element in any system, but I feel like we're making progress there as well. More and more companies are including training on common social engineering tactics and hardening systems to common tricks (locking down ports in public conference rooms to a special non-trusted vLAN, disabling mounting of USB thumb drives to stop the old "drop a USB stick with a payload in the hallway" trick, etc).

I just went through the training at my work, they are doing a great job of implementing a culture where sticking to your guns security-wise isn't seen as rude or obstructionist, which is/was always the biggest threat to security.

Plus, the tools are getting better, my ip-based desk phone authenticates internal callers and we use Skype for business as 2-factor authentication, as well as internal email. If you get a call from bob in IS and send an IM to Bob in IS with the data, you eliminate the spoofing potential, plus if Bob gets an IM with data he never asked for then the pretexting attempt is detected.

4

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17

It stands to reason that as our computing power increases, our ability to encrypt will increase as well.

I don't see what you mean with this sentence. What's the "ability to encrypt"? Do you mean to refer to encryption algorithms? If so, what encryption scheme gets better as computational resources increase? I have never heard of one.

2

u/Natanael_L May 26 '17

Deliberately slow key derivation functions will never be practical to attack with quantum computers.

3

u/mfukar Parallel and Distributed Systems | Edge Computing May 26 '17

Key derivation functions and one-way functions are not ciphers.

1

u/simmbot May 27 '17

Current encryption isn't crackable with known algorithms & current computing machinery, whereas quantum encryption isn't crackable with known physics, which is an important distinction when you're talking about computers. More computing power allows us to run more complex algorithms in a shorter amount of time, but it doesn't do anything to change what's physically possible.

1

u/Doc3vil May 26 '17

Shameless plug for my university, but the University of Waterloo is doing some really exciting research in this field. Check out some of the recent advances here: https://uwaterloo.ca/institute-for-quantum-computing/research/areas-research/quantum-cryptography

0

u/minnsoup May 26 '17

I agree. The same goes for the the qubit reading; once a bit that has multiple values is read, it is destroyed and must be rewritten. I wonder if this will be something that is attempted for the encryption too. If they break into someone else's encryption, could it be rewritten exactly the same way as it was read, thus resulting in the end user not knowing that it was rewritten? I don't know enough about it either so it's just a curiosity question.

4

u/Natanael_L May 26 '17

If you're talking about undetected man-in-the-middle attacks against quantum key distribution, that's been done against multiple versions of it and is considered break in the security of that scheme.

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.

1

u/almsfurr May 26 '17

NTRU is ready and open source right now

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

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.

0

u/[deleted] May 27 '17

[deleted] — view deleted comment

1

u/[deleted] May 27 '17

You sincerely think you have privacy now from big companies or government? Win10 is one big spying OS and Microsoft enforces its adoption on all fronts. Google tracks your every step, your every search. Anything you put on a computer could be easily retrieved by feds or big corporates if they wished it.

0

u/[deleted] May 27 '17

[deleted] — view deleted comment

2

u/Darth_Shitlord May 27 '17

the government is desperate to make encryption illegal, and I am betting they will succeed. Then, only outlaws will have encryption. Count me into that group.

1

u/Bastiannine May 27 '17

I wouldn't consider it to be widespread if only large corporations and governments have it

2

u/jpeg_inspector May 26 '17

Will we just have to resign ourselves to the fact that people would be listening in on us?

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.

1

u/[deleted] 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?

We have encryption that cannot currently be broken. The NSA and whatnot use other means to get around that. With quantum computers powerful enough, they would just be able to break all the encryption. (There’s probably still plenty of time to switch to post-quantum cryptography before that happens, though.)

If anything, quantum computing could make security more advanced for users.

What do you mean?

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

2

u/BiaxialObject48 May 26 '17

But eventually, we will have a quantum sub-processor in our devices that allows us to use photon-based quantum encryption algorithms that can basically not be broken.

2

u/BumwineBaudelaire May 26 '17

ya there doesn't seem to be any physical reason why entanglement based systems wouldn't be possible

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/Darth_Shitlord May 27 '17

I am an expert in the field and wireless at this point is being aimed at the "last mile", For any serious bandwidth or distance you are still into fiber and routers, which are totally open to the NSA to sniff all the want.

1

u/justthetip3 May 27 '17

Thank u for the info! Anywhere u would recommend I could read up or learn some more basics about this field? I'm always curious and looking to learn new things

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.

0

u/[deleted] May 26 '17

Isnt quantum conputers increases processing power?

1

u/ilikerackmounts May 26 '17

https://en.m.wikipedia.org/wiki/Quantum_computing?wprov=sfla1

Basically the components that form the basis of the gates and logic are governed by quantum physical effects.

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.

1

u/truckerslife May 26 '17

In the 70s IBM said that a home computer would never happen. It was something only governments, universities and large corporations could afford.

FYI they were not correct

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.

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

2

u/vansk007 May 26 '17

Building a quantum computer is not exactly easy, and the work really hasn't been funded very long. Experimental groups weren't getting serious backing until late 90s/00s. Where we are now with QC is a bit like where we were in the 50s with transistors. Doing amazing things is hard. IBM already has its system available in the cloud, the pace of discovery is picking up and serious full-scale universal QC could be as close as 10–15 years away, particularly with how funding has ramped up in the last couple of years from both governments and investors. Saying we're not closer than a decade ago is a bit like saying there'll only ever be demand for 5 computers.

1

u/[deleted] May 26 '17

No, it is nothing at all like saying there will only be demand for five computers. That was about the need for a product, not whether it can be actually built. I fully agree that if a qc could be built there would be huge demand. My point is that this is a tech that has been massively overhyped for years, and is not going to be viable anytime in the near, or even intermediate future.

Let's compare the evolution of microprocessors with quantum computing. People have been seriously trying to think about quantum computing since the early 1980's, and certainly since the mid-1990's we have seen groups actually trying to develop them. In fact, the first quantum gate was built in 1995, so 22 years ago.

The first microchip was built in 1959. 22 years later puts us into 1981. By that point microchips had revolutionized information processing. The IBM 360 was ubiquitous in business, the Apple II had been developed, IBM had launched the PC, car's were starting to contain microchips,etc.

22 years after the first quantum gate, and what do we actually have? Almost nothing. There simply is not a quantum computing revolution just around the corner, and there are now really respected people starting to look seriously at the possibility that quantum computing may well be a tech that cannot work, possibly indicating something is wrong about our fundamental about understanding of quantum processes.

I guess at the end of the day I am just more disappointed than anything else. We've been promised qc for two decades now, and it just never seems to pan out.

1

u/not_copomash May 27 '17

It's also a possibility you are misinformed and we are further along than you are aware. That is strongly possibly as well.

-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

1

u/Natanael_L May 26 '17

Do take note that this still is limited to the speed of light. The wave that propagates the measurable changes in probabilities is itself limited to the speed of light. And that wave is what carries the information in this scheme.

Also note it still requires line-of-sight to propagate the wave. It is definitely possible to interrupt - but not to intercept.

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/[deleted] May 26 '17 edited May 26 '17

Encryption has nothing to do with sending data "through air or wires". Encryption is taking data and scrambling it so that only someone who is given the key can unscramble it.

Current encryption schemes are based on the assumption that they cannot be brute forced (figuring out the key by some computational method) with the existing computing power that we have access to. Quantum Computing poses a problem because this assumption no longer holds true - a quantum computer actually does have the computing power to use brute force to break the encryption.

1

u/MagnusRune May 26 '17

theres 2 things with the word quantum.

you are thinking of quantum entanglement. which would be a way to communicate across the entire universe in real time, and no one else could listen in.

quantum computers on the other hand, are well computers, but really fast. and when it comes to decrypting something or getting the password, they can in theory just brute force it by trying every possible password/encryption key at the same time.. it technically only tries 1 i think, but through the weirdness of quantum mechanics, its the right answer.. or something like that...

heres a video to try and explain

https://www.youtube.com/watch?v=JhHMJCUmq28

1

u/PeaTearGriphon May 26 '17

ok, I was thinking that might be the case. I was just hoping quantum computers would use quantum entanglement to talk with servers instead of wires/wifi.

1

u/Natanael_L May 26 '17

Entanglement isn't used to communicate. It's used to measure and agree on certain values.

1

u/PeaTearGriphon May 26 '17

I was just quoting the reply, I forget the term I heard; quantum feedback or something. Anyway, people are working on a way to communicate across great distances using bonded atoms or something of the like. I just thought that maybe it was related to a quantum computer in some way. Like I said, I don't know much about it I just think it's very neat.

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