GCHQ on Quantum Key Distribution

The UK’s GCHQ delivers a brutally blunt assessment of quantum key distribution:

QKD protocols address only the problem of agreeing keys for encrypting data. Ubiquitous on-demand modern services (such as verifying identities and data integrity, establishing network sessions, providing access control, and automatic software updates) rely more on authentication and integrity mechanisms—such as digital signatures—than on encryption.

QKD technology cannot replace the flexible authentication mechanisms provided by contemporary public key signatures. QKD also seems unsuitable for some of the grand future challenges such as securing the Internet of Things (IoT), big data, social media, or cloud applications.

I agree with them. It’s a clever idea, but basically useless in practice. I don’t even think it’s anything more than a niche solution in a world where quantum computers have broken our traditional public-key algorithms.

Read the whole thing. It’s short.

Tags: authentication, cryptography, economics of security, encryption, GCHQ, keys, quantum computing, quantum cryptography

Posted on August 1, 2018 at 2:07 PM • 21 Comments

Comments

statetheobvious • August 1, 2018 2:30 PM

“By contrast, post-quantum public key cryptography appears to offer much more effective mitigations for real-world communications systems from the threat of future quantum computers.”

I think come quantum computers we would change the alogrithms of encryption wihile the public/private key structure would remain untouched.

Humdee • August 1, 2018 2:35 PM

“…in a world where quantum computers have broken our traditional public-key algorithms.”

Dubious this will ever happen.

justinacolmena • August 1, 2018 3:41 PM

address only the problem of agreeing keys for encrypting data.

A key ingredient is missing.

rely more on authentication and integrity mechanisms — such as digital signatures — than on encryption.

With whom are we (Alice) agreeing on keys for encrypting data? Yes, the missing ingredient is the identity of the other party (Bob) to the communication. But “they” (Eve, Mallory, et al.) are driving a hard bargain for us to give up encryption entirely in exchange for something else.

Mp • August 1, 2018 9:23 PM

I read the article and maybe this is my ignorance of cryptography showing but why is it an issue if QKD is inherently point-to-point? Why wouldn’t that replace the encryption part of public-key crypto schemes that we currently have? Where does the theory break down?

As far as equipment cost and range is concerned, I’m assuming the former is a matter of time before it’s cheaper and I am assuming (perhaps erroneously) that future research will address the issue of short range.

justinacolmena • August 1, 2018 10:45 PM

if QKD is inherently point-to-point?

Oh, yeah. It’s like Bluetooth. The same code shows up on both ends. Sure. Don’t touch my music.

Otherwise, maybe Alice thinks she is talking to Bob, but in reality she is talking to Eve, who is secretly giving Alice a haircut before passing her information on to Bob and creatively reinterpreting Bob’s response for her to create an altered worldview for Alice’s benefit — rationalizing that what Alice doesn’t know won’t hurt her.

Lawrence D’Oliveiro • August 2, 2018 12:44 AM

Quantum computers have so far proven totally useless at anything resembling number-theoretic problems (e.g. cracking encryption). The only kinds of problems they have so far been able to attack have been physical simulations, where they can produce answers quicker than, but with less accuracy than, regular digital computers.

In other words, “quantum” computers are nothing more than old-style analog computers reborn.

65535 • August 2, 2018 1:00 AM

Great.

I click on the GCHQ link Bruce S. has and my browser ad on notes that “Although is address appears to come form a different country is served from an IP in the USA.”

Sure, it could just be GCHQ using a CDN or the like. But, I also could come from Fort Meade. The trust in the content melts rapidly.

As Clive Robinson has noted IP are difficult to properly locate.

Peter Galbavy • August 2, 2018 2:12 AM

I am sure the hipsters have been working on their Power Points combining QKD with Blockchain already…

Mr. C • August 2, 2018 2:44 AM

@ MP:

I’m not exactly the best qualified person for this task, but here goes:

QKD solves the problem of “how do I establish a shared secret with a known counterparty when there may be eavesdroppers on the communication channel?” (QKD is guaranteed to fail if eavesdropped upon, so a successful exchange implies no eavesdropping occurred.)

The main thrust is that this isn’t the problem that needs solving. The problem that needs solving is “how do I know my counterparty really is who they say they are?” This is a really hard problem to which there are no good solutions short of a face-to-face meeting with someone you’ve known since childhood. Presently we rely on faulty-but-it’s-the-best-we’ve-got methods like “certificate authorities” to “solve” this problem. The ability to securely exchange a key doesn’t do you any good if you’re securely exchanging a key with an imposter.

Moreover, the problem QKD solves can be solved in other ways. You can make a key exchange out of any asymmetric algorithm. The security assurance is “secure so long as the eavesdropper doesn’t own a practical quantum computer and hasn’t found a fast classical solution to a problem generally believed not to have one.” (The quantum computer bit drops out if you use a “post-quantum” algorithm, at the cost of the exchange being slower and more bandwidth hungry.) This guarantee isn’t as good as QKD’s “physics says eavesdropping is impossible,” but it’s good enough, and at least as good as every other part of the system.

echo • August 2, 2018 5:38 AM

Read the whole thing. It’s short.

Please no! I want to stay awake.

The main thrust is that this isn’t the problem that needs solving. The problem that needs solving is “how do I know my counterparty really is who they say they are?”

From all the public comments from people who have gone through the process enhanced vetting isn’t pleasant for them or their friends or their friends friends.

I think GCHQ hire people who weren’t exciting enough to be auditors.

Bill • August 2, 2018 8:32 AM

Note that the GCHQ whitepaper is actually from October 4th, 2016. So it is older than I would have expected.

Does any one know if there have been any similar position whitepapers on QKD from other governments (US or other)?

I am aware of the NIST work on post quantum crypto (https://csrc.nist.gov/Projects/Post-Quantum-Cryptography), but I have not seen an explicit statement regarding QKD.

One other point is that various sources (IBM, NIST) are indicating that a viable quantum computer for attacking classic asymmetric crypto (RSA, ECC, …) might be viable in the 2030 time frame.

For those of us designing systems and equipment that will be in service for 20 to 30+ years in critical infrastructure applications, we might reasonably expect that our crypto implementations will become obsolete during the service life of the equipment.

With some of classic crypto algorithms baked in to hardware, there are no easy solutions here.

Clive Robinson • August 2, 2018 1:06 PM

@ All,

There appears to be nothing in the white paper “technically” that has not been said on this blog in much greater depth over the years

As for GCHQ ey al’s position on QKD there are some very very few occasions when it can be of use, but those realy are esoteric uses currently.

So my view point about QKD is “it’s a waste of resources”….

Weather • August 2, 2018 1:20 PM

Yeah you could simulate a quantum computer with a anlog computer, but if you wanted to match a digital computer you would need to have at least 257volts with one volt incremental, the quantum is just a byte where as digital is 2 bit it in theory can be made small physically from digital which is pretty much Moore law, making the move to quantum. I tried designing a anlog computer out of resistor capacitor and inductor which could have been built in the back shed, but power size cost wouldn’t make it a good choice, the only bounes is at a modern mafactue place you probably get serial cores up to Thz speed. I think people are getting confused with it can be both up and down at the same time, encryption code XOR and or not if statements only work on one branch, so if it’s up and down and you and it, with just up, the answer will be up and down or zero, we’ll that’s the way I see it.

echo • August 2, 2018 1:53 PM

@Clive

Judging by some of the rushed papers on GCHQs website I suspect they are trying to fill space and appear relevant. My local councils website has similar filler ordered by the yard.

This is more a squid topic: While researching lawyers perspectives on the general subject area of security I have discovered they are equally weak. I also discovered a grendade buried in the Law Societies advice which if they discovered one of their own clients had been mistreated like this would have them spitting bullets. Enter ‘Mishcon de Reya’ complaining to ICO about anti tax evasion methods. It’s a curious case of how the rich and powerful try to corrupt systems to evade identification and scrutiny.

Dave • August 3, 2018 12:30 AM

QKD is nothing more than a phenomenally expensive, range-limited, complex way of doing Diffie-Hellman key agreement from forty years ago. It’s an impractical solution to a problem we don’t have.

Having said that, it’s a great way to sell really expensive magic black-box hardware to banks who don’t understand the issues involved.

MarkH • August 3, 2018 12:45 PM

Real-World Situation has Developed Not Necessarily to QC’s Advantage

Quantum computing and cryptography are like many technological whiz-bangs of the past and present: lots of breathless claims of their tremendous power and promise, and relentlessly disappointing results.

This isn’t directly connected to crypto, but is yet another smack-down for QC:

So far (AFAIK), no “quantum machine” has done any useful task significantly better than can be done by more conventional means.

There are a few problems which quantum computers (if they could ever be scaled up to useful size) are supposed to be able to solve dramatically quicker than “classical” computers … actually, very few problems.

Best know to crypto people is Shor’s algorithm for the factoring of semi-primes and finding of discrete logs. Huge impact on cryptography (if it ever comes real), but a very narrow problem domain.

Another of those very few problems for which QC was supposed to make a huge speed-up is the “recommendation problem,” essentially a problem in navigation of an ultra-large matrix.

Until now … 18-year-old Ewin Tang has found a classical computing solution comparable in speed to the hypothetical quantum computation.

So, the short list has gotten even shorter.

Aptly enough, Tang (an extraordinarily keen mathematician who at 18 is starting his Doctoral program) is a student of Scott Aaronson.

Aaronson is perhaps the world’s best-informed “quantum skeptic.” Not a quantum physics researcher himself (Aaronson’s specialty is algorithms and complexity theory), he has followed QC developments with great attention.

Though Aaronson looks at QC with an open mind (he’d be as pleased as anyone to see them actually work), his perspective is skeptical … because reality. It was he who brought the recommendation problem to Tang’s attention.

echo • August 3, 2018 2:26 PM

@MarkH

I think I read this week an article which explained how mathematciians are breaking problems down into what can be solved classically or quantum, or both. Apparently they found one problem which is a quantum only problem. Some problems they don’t know the classification for yet.

I’m sorry I can’t remember where I read it.

Sandro Fontana • August 7, 2018 4:36 AM

“It’s a clever idea, but basically useless in practice.”
I absolutely agree with that.

The schema has always needed to add an authentication mechanism.

Only in the case of a point-to-point connection could have been avoided, but … service/price ratio is not adequate

Andrew Yeomans • August 7, 2018 9:35 AM

@MP, @Mr.C
As Mr. C says, QKD actually addresses the problem of sharing secrets with another party. You might use these secrets as an encryption key, or might use them as a proof of identity. (Here identity means “this is the same person as the previous time”.)

So if the two parties share (say) 2 Kbit of secrets, they can use a one-time-pad process to perform 20 authentications of 100-bit strength – just like banking TAN codes – with provable security (through information theory).

Alternatively they can re-use some of those secret bits via a cryptographic primitive that is believed to be quantum-resistant, maybe a hash function in TOTP/HOTP style, to confirm identity. This re-use doesn’t keep consuming the secrets, but does not carry the same provable security as a one-time-pad, but then neither are current public key algorithms provably secure.

It’s quite possible to create public key algorithms from shared-secret primitives, see the paper https://uhra.herts.ac.uk/bitstream/handle/2299/4350/201404141252.pdf for some methods, which demonstrates that most of the supposed advantages of asymmetric algorithms are largely mythical, especially when looking at the entire infrastructure of CAs, OCSP, etc that are required.

Unclear • August 7, 2018 11:33 AM

QKD is such a buzzword, but Einstein would find it amusing, since he’d argued all through the last thirty years of his life that (effectively, given that in his day there was no encryption in the modern sense) – thewholedatastream – including keys, could be done with quantum entanglement. None of his contemporaries agreed, but I personally believe Einstein’s contention that the observation/decoherence mumbo-jumbo is only an illusion of the experiment’s mechanics.

Unclear • August 7, 2018 12:08 PM

The previous post was a little unclear (hehe). To clarify, Einstein didn’t believe that the use of entanglement was limited to the verification function.

GCHQ on Quantum Key Distribution

Comments

Leave a comment Cancel reply