Live data from Hacker News

Cryptographers achieve perfect secrecy with imperfect devices

quantamagazine.org

21–30 of 34 posts

Re: Cryptographers achieve perfect secrecy with imperfect devices

#21
post #6

> The universe hadn’t decided what the value would be before it was measured,” said Colbeck. “That’s the origin of the security.” My naive security architect view is, I get the impression the people doing quantum engineering and those working as cryptographers have a very narrow overlap. Reading about quantum key agreement/distribution (QKD), it's different from cryptographic functions where you have things like conv…

> My naive security architect view is, I get the impression the people doing quantum engineering and those working as cryptographers have a very narrow overlap. Correct. It's also the difference between theoretical security for infinite time vs security for something like 10^30 years. Is it really worth changing tried and tested algorithms and implementations already in place?

The asymmetric encryption/key-exchange algorithms that survive large quantum computers are all quite experimental and each has at least one major downside compared to RSA and (EC)DH. Still I'd prefer them over QKD.

Re: Cryptographers achieve perfect secrecy with imperfect devices

#22

First author of one of the preprints mentioned in the article here (theory in Paris/Geneva/Zürich/Lausanne, experiment in Oxford) – happy to answer any questions! I obviously speak only for myself, not for any of my colleagues, and as a matter of course, I should also mention that publication in a peer-reviewed journal is still pending for these results. One point to mention — which I feel quite strongly about, and I…

> Rather, device-independent quantum key distribution allows you to scale back the assumptions on your implementation to a well-motivated, minimal set. To me, this is already intriguing enough without the need for hyperbole! Would it be accurate to say it is scaled back to the level achieved by classical (non-quantum) cryptography?

> Would it be accurate to say it is scaled back to the level achieved by classical (non-quantum) cryptography?

Not quite. Classical cryptography of course requires the additional assumption that the computational capacity of the attacker is limited (at least if the amount of key material available is less than the length of the messages to be exchanged). QKD does not need any such computational assumptions. Looking at this purely from a theoretical perspective, I hope you'll agree that the ability to create new shared randomness "out of thin air" by drawing on quantum correlations, and to do so an information-theoretically secure fashion, is a pretty neat trick.

Now, if you asked me how likely it is _in practice_ that $THREE_LETTER_AGENCY has broken your cryptosystem to the point where they can feasibly attack it/have backdoored it, compared to the likelihood that they've bugged your devices in a supply chain attack or found any number of other ways to compromise the practical implementation, I suspect my answer wouldn't be much different to yours. Nevertheless, I still think it is interesting to explore additions to the cryptographer's toolbox that, in a very practical sense, have a rather different profile of assumptions and tradeoffs.

Re: Cryptographers achieve perfect secrecy with imperfect devices

#23

First author of one of the preprints mentioned in the article here (theory in Paris/Geneva/Zürich/Lausanne, experiment in Oxford) – happy to answer any questions! I obviously speak only for myself, not for any of my colleagues, and as a matter of course, I should also mention that publication in a peer-reviewed journal is still pending for these results. One point to mention — which I feel quite strongly about, and I…

can you link the preprint by chance? I can never find the actual papers from quanta...

Re: Cryptographers achieve perfect secrecy with imperfect devices

#24
post #12

First author of one of the preprints mentioned in the article here (theory in Paris/Geneva/Zürich/Lausanne, experiment in Oxford) – happy to answer any questions! I obviously speak only for myself, not for any of my colleagues, and as a matter of course, I should also mention that publication in a peer-reviewed journal is still pending for these results. One point to mention — which I feel quite strongly about, and I…

The first sentence of your paper abstract is: Cryptographic key exchange protocols traditionally rely on computational conjectures such as the hardness of prime factorisation to provide security against eavesdropping attacks. Remarkably, quantum key distribution protocols like the one proposed by Bennett and Brassard provide information-theoretic security against such attacks, a much stronger form of security unreach…

> QKD is no replacement for asymmetric cryptography since it requires exchanging a secret key before the communication can take place.

Your general point about QKD "promises" vs. practical IT security is well taken, particularly as I am much more of a general quantum physicist and spare-time compiler/infosec geek than a QKD person myself.

However, note that asymmetric cryptography doesn't really solve the authentication problem you mention either. If you don't want to place your trust in some sort of PKI, you are back to Alice and Bob having to meet first to exchange some sort of key material (e.g. their public keys) to later avoid impersonation. Given an authenticated channel, both QKD and classical public-key cryptography can construct a secure channel for messages of arbitrary length, but the latter only for computationally bounded attackers. Of course, this is not to say that a trusted PKI can't be a sensible assumption in practice.

Re: Cryptographers achieve perfect secrecy with imperfect devices

#25

Earlier quoted context omitted.

> Rather, device-independent quantum key distribution allows you to scale back the assumptions on your implementation to a well-motivated, minimal set. To me, this is already intriguing enough without the need for hyperbole! Would it be accurate to say it is scaled back to the level achieved by classical (non-quantum) cryptography?

> Would it be accurate to say it is scaled back to the level achieved by classical (non-quantum) cryptography? Not quite. Classical cryptography of course requires the additional assumption that the computational capacity of the attacker is limited (at least if the amount of key material available is less than the length of the messages to be exchanged). QKD does not need any such computational assumptions. Looking a…

Oh absolutely, the theory behind QKD is fascinating! And I do think that some day there may be actually secure practical implementations, maybe even ones that are practical for more than a few niche applications.

But you mentioned the assumptions on the implementation, not on the underlying mathematics. The thing that concerns me is that QKD introduces additional hardware to operate, and there have been many demonstrations of weaknesses in that hardware that threaten the overall security of the system. With DIQKD you ensure that those issues no longer affect security (again it is absolutely remarkable that this is possible at all), but now you still have to concern yourself with all the implementation vulnerabilities that also plague classical cryptography. In that sense I mean that the implementation assumptions are now the same.

Re: Cryptographers achieve perfect secrecy with imperfect devices

#26

> The universe hadn’t decided what the value would be before it was measured,” said Colbeck. “That’s the origin of the security.” My naive security architect view is, I get the impression the people doing quantum engineering and those working as cryptographers have a very narrow overlap. Reading about quantum key agreement/distribution (QKD), it's different from cryptographic functions where you have things like conv…

> My naive security architect view is, I get the impression the people doing quantum engineering and those working as cryptographers have a very narrow overlap.

You probably aren't wrong, but also note that popular science articles are probably not the best basis for judging this. :) A number of people working on QKD have done serious work on classical cryptosystems as well, although the overlap of that set with people working "in the trenches" of practical IT security is of course yet another topic.

> To do the data exchange, it's not encrypted to a key per se […]

I'm not sure whether this is what you are wondering about, but the actual data exchange is completely separate from the key distribution. Particularly for the entanglement-based protocols like used in device-independent scenarios, there isn't really any data exchange between the parties during the key distribution stage at all (apart from the classical post-processing steps such as error correction after the fact). Rather, the quantum resource provides random, but correlated bit strings at the two nodes. Only after the QKD protocol has finished is there actual data exchange using the secret key material, probably using the key as a one-time pad to keep the information-theoretic security guarantees.

Thus, trying to think about these protocols in terms of data transfer doesn't strike me as particularly natural; in fact, if the entangled state shared between Alice and Bob is maximally entangled, the raw bits obtained from the quantum devices are always going to be completely random.

The security proofs are indeed based on careful entropy considerations. You mentioned implementation details of classical cryptosystems. These primitives – S-boxes, etc. – motivate why we should reasonably expect cryptanalysis on such algorithms to be hard in practice, even though we know that they can't be secure considering information theory only. In the QKD case, however, we can make information-theoretic security statements without any reference to computational power. Thus, a security analysis will look at quite a different set of things: on one hand, whether the entropy accounting is correct, and on the other hand, whether the practical implementation actually corresponds to what that accounting assumes.

Re: Cryptographers achieve perfect secrecy with imperfect devices

#27
post #12

Earlier quoted context omitted.

The first sentence of your paper abstract is: Cryptographic key exchange protocols traditionally rely on computational conjectures such as the hardness of prime factorisation to provide security against eavesdropping attacks. Remarkably, quantum key distribution protocols like the one proposed by Bennett and Brassard provide information-theoretic security against such attacks, a much stronger form of security unreach…

> QKD is no replacement for asymmetric cryptography since it requires exchanging a secret key before the communication can take place. Your general point about QKD "promises" vs. practical IT security is well taken, particularly as I am much more of a general quantum physicist and spare-time compiler/infosec geek than a QKD person myself. However, note that asymmetric cryptography doesn't really solve the authenticat…

All of this is correct. But I still think it is misleading to create the impression that QKD could be a replacement for RSA. Especially, since asymmetric cryptography and PKI are cornerstones of the modern internet. Why don't you change the abstract and cite Rijndael or something like that? Your work is a very impressive achievement, I am sure Nature will publish it either way.

Re: Cryptographers achieve perfect secrecy with imperfect devices

#29
post #28

Is this a how to distribute a OTP using quantum mechanics?

Essentially, yes; all of quantum key distribution (QKD) is generating a secret key which can then e.g. be used as a one-time pad. The novelty here is that we can do it with much fewer assumptions on how the quantum devices behave than in conventional QKD.

Re: Cryptographers achieve perfect secrecy with imperfect devices

#30
post #11

First author of one of the preprints mentioned in the article here (theory in Paris/Geneva/Zürich/Lausanne, experiment in Oxford) – happy to answer any questions! I obviously speak only for myself, not for any of my colleagues, and as a matter of course, I should also mention that publication in a peer-reviewed journal is still pending for these results. One point to mention — which I feel quite strongly about, and I…

I always read perfect secrecy as a term of art with some technical meaning. This protocol seems to solve the communication at a distance problem for which asymmetric encryption was developed but since then a lot of other uses for public key, e.g. signing and multi-party decryption and so on have come out of public key. Do you think there will be entanglement based replacements for these?

> a lot of other uses for public key, e.g. signing and multi-party decryption and so on have come out of public key

To the best of my knowledge, multi-party decryption isn't really related to public key cryptography. Sending a message to a single recipient looks like this:

1. You write a message.

2. You encrypt it with a symmetric algorithm.

3. You encrypt the key to the encryption in step (2) with an asymmetric algorithm, using your recipient's public key.

4. You send them the combined message, encrypted ciphertext plus encrypted key-to-the-ciphertext.

5. They use their private key to decrypt the key-to-the-ciphertext.

6. They decrypt the message using the key you just sent them.

It's done that way, as far as I've learned, mostly because symmetric encryption is faster than asymmetric encryption.

But multi-party decryption is exactly the same:

1. You write a message.

2. You encrypt it with a symmetric algorithm.

3. You encrypt the key to the encryption in step (2) using the various public keys associated with each of your intended recipients.

...

So instead of a single-recipient message being a ciphertext accompanied by a header revealing the encryption key to the ciphertext, a ten-recipient message is a ciphertext -- exactly the same ciphertext! -- accompanied by ten headers, each of which is only readable by a particular private key. There's nothing about this method that draws on public key cryptography; if I've exchanged OTP material with each of ten people, I could send a multi-recipient message exactly the same way. (And doing so would be at least as valuable as it is in the public-key case -- doing things that way allows me to send a message of arbitrary length while only consuming a bounded amount of OTP material.)

Post reply on HN