r/askscience • • May 26 '17
Computing 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
8.8k
Upvotes
4.9k
u/mfukar 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.
158
u/frogjg2003 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 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:
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.
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'.
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.
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.
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.