How does quantum encryption work?

Question

There has been a lot of buzz about quantum computing especially with D-Wave breaking the limits each month. I have basic knowledge about cryptography with an introductory course in quantum computing.

So, how does quantum encryption work? and how is it different in principle from the current practices adopted?

Answer 1

There are a few key distinctions to make

Quantum cryptanalysis

This is what you hear all the buzzing about. Specifically, there is something called Shor's algorithm, that when used to break modern crypto, can be devastating. If you've encrypted a zip file and told someone the key you're quite safe. But things like PGP and SSL, where you have to agree to a key online, might be vulnerable if they are based on factoring numbers like RSA. Quantum algorithms have about an impact of O(n/2) on symmetric crypto decrease the effective key size by half for everything else, such as symmetric crypto and more resistant asymmetric crypto. That means AES-256 will be as strong as a pre-quantum AES-128. RSA will be much worse off:

Shor’s Algorithm, which can only be executed on a quantum computer, can factor large numbers in $\log(n)^3$ time, which is drastically better than the best classical attack. [Normally RSA2048] takes about $10^{41}$ units of time ... Using Shor’s algorithm, the same problem only $10^3$

This is not something D-Wave can do yet. As far as we know.

Geordie (chief technology officer of D-Wave) on June 2, 2011, at 3:59 pm said:

We do have a factoring algorithm that I’m going to do a series of blog posts on (the working title is “Better than Shor” :-) ).

-- https://dwave.wordpress.com/2011/05/11/learning-to-program-the-d-wave-one/

After that they never mentioned this again. Either he was wrong or someone told him to shut up about it.

Quantum Key Distribution

This is what the other answer mentions, and this is something we can do today, and because of that, there's some hype about it. What it comes down to is that you have a guarantee that the code has not been intercepted in transit, because any observation would affect the quantum state. But it's really slow for now.

Post-quantum cryptography

These are simply crypto schemes designed to withstand algorithms like Shor's. An implementation is McElieces'; some fascinating work based on the hardness of breaking linear error-correcting codes. Other asymmetric implementations are based on lattices.

Answer 2

Quantum key distribution takes advantage of physics to create a communication channel that can't be cleanly intercepted without corrupting part of the message. This can be used to create a shared secret key for a one-time pad to be used over a classical connection.

Particles may have a quantum state which can be thought of as having multiple bases (such as rectilinear or diagonal polarization) where only one of the bases may be measured before the state is reset. If you measure the particle in one basis, then you've modified its state and can no longer go back and measure the particle in another basis. An eavesdropper trying to intercept a communication made in the quantum states of a series of particles needs to know which basis to read and write in, otherwise the eavesdropper will get the useless value from the wrong basis and corrupt the value in the correct basis.

Alice sends Bob a series of particles where for each particle, Alice chooses a random basis, and then sends a random value on that basis. For each particle, Bob picks a random basis to measure the particle by. After Bob has measured the particles, Alice and Bob tell each other (over classical channels) the basis they used for each particle in the sequence. They throw away all of the values where they picked different bases, and construct a key out of the values where they each used the same basis. If an attacker Eve was intercepting the particles, then Eve would have read and wrote some of the particles in the wrong basis, and Alice and Bob can determine they got different values for some of the particles that they chose the same basis for.

In practice, some error rate is naturally expected, and Alice and Bob can do some error correction to recover and still construct a shared key if the error rate is low enough. There's more information on the wikipedia page: https://en.wikipedia.org/wiki/Quantum_key_distribution

Answer 3

In addition to the other answers, I want to add that D-Wave makes a type of machine called an Adiabatic Quantum Computer, which is fundamentally different from the general-purpose quantum computers capable of running Shor's algorithm. D-Wave's machines are good at optimization problems, but have zero applicability to cryptography. Moreover, it's not even clear that D-Wave's machines are "quantum computers" in the full sense of the word:

"it is still unknown whether D-Wave's machine actually harnesses quantum mechanics to offer a computational speed-up," wrote Martin Laforest, a senior manager for scientific outreach at the University of Waterloo's Institute for Quantum Computing. [source]

So, despite D-Wave's marketing department being good at generating loud headlines, please don't take this as a measure of progress towards cryptanalytic quantum computers.

Answer 4

Secure communication over a noise-free quantum channel does not require encryption algorithms such as AES; an adversary can't intercept information from a quantum channel - the best he can do is to destroy the channel. But this is true only if we have a noise-free channel. If we have a noisy quantum channel, we need no use quantum error detection and error correction algorithms, and using these algorithms potentially opens a backdoor for an adversary - this is an interesting story.

But probably your term "quantum encryption" actually means "post-quantum cryptography", that is classical encryption algorithms secure against attacks using quantum computer - see wikipedia