4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This article is from a security conference presentation that covers both QC and QKD. arxiv.org/abs/1609.09157 $\endgroup$ – nonce Jan 27 '17 at 20:27
9
$\begingroup$

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 zipfile and told someone the key you're quite safe. But things like PGP and SSL, where you have to agree to a key online, are vulnerable; quantum algorithms have about an impact of O(n/2) on symmetric crypto decrease the effective key size by half for symmetric 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 realy slow for now.

Post-quantum cryptography

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

$\endgroup$
  • 2
    $\begingroup$ Quantum algorithms have about an impact of $O(n/2)$ on symmetryc crypto This is incorrect. We do not compare the key size in such a way via complexity. While the idea of the effective size of the key is divided by 2, the Grover algorithm allows a speed up of $O(\sqrt{n})$. Which, given a key size of $n$ bits, thus a search size of $2^n$ an effective search of $\sqrt{2^n} = 2^{n/2}$. The effective size of the key (if you were to compare to a pre-quantum size) is divided by 2, but the complexity of the search is $O(\sqrt{n})$ where $n$ is the size of the search space. $\endgroup$ – Biv Jan 27 '17 at 5:11
  • $\begingroup$ I didn't know that, thanks so much :). My post was mainly to counterbalance the other post, which only went into QKD. $\endgroup$ – J.A.K. Jan 27 '17 at 14:58
  • $\begingroup$ It's worth saying that there isn't consensus yet on whether D-Wave really is a quantum computer. IBM has granted open access to their 5 qbit quantum processor though, so I think that stands as a better example of future threats. MIT is working on breaking RSA with a 5 qbit processor. Also worth noting, QKD can be compromised by spoofing distributions to match the Bell test. $\endgroup$ – nonce Jan 27 '17 at 21:00
  • 1
    $\begingroup$ A bit aside, but nevertheless related to the quantum cryptanalysis section: What does a “real” quantum computer need for cryptanalysis and/or cryptographic attack purposes? That Q&A goes well beyond the hyped D-Wave and might therefore represent a more valid reference for your “As far as we know.” $\endgroup$ – e-sushi Jan 29 '17 at 18:37
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks. This was worded simply enough that I could understand it on an intuitive level, without any supplemental reading. $\endgroup$ – Venryx Nov 26 '17 at 16:13
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The media does do a great job throwing everyting under one umbrella if there are buzzwords like 'quantum' involved. $\endgroup$ – J.A.K. Jan 27 '17 at 16:20
  • 1
    $\begingroup$ @J.A.K. And I can't even blame them; outside of a few specialized quantum computing institutes, even grad students in math / computing / physics have troubles getting the facts straight about quantum computers. I can't even blame the journalists... $\endgroup$ – Mike Ounsworth Jan 27 '17 at 16:25
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.