Cryptographers achieve perfect secrecy with imperfect devices
quantamagazine.org
quantamagazine.org
One point to mention — which I feel quite strongly about, and I think my collaborators do as well – is that sweeping generalisations like "perfect security" are really not the point, and, if anything, have mostly done the field a disservice. Such statements do make for catchy headlines, and while there is a solid technical meaning attached to them (information-theoretic security), to a wider audience they might suggest that QKD replaces the need for careful security engineering, which is definitely not the case: if your processing nodes, say, leak out the generated key material via a classical side channel, no amount of theoretical security guarantees will save you!
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!
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?
That's indeed the case, but I fear the subtle technical definition here is usually one of the first things to go in the cycle of press releases and news articles, entirely too quickly giving rise to headlines that speak of “unhackable cryptography" or things like that. I've slightly edited my above post to clarify this, thanks.
> Do you think there will be entanglement based replacements for these [other protocols]?
One thing to note is that QKD is fundamentally a primitive to create shared, private randomness, not a communication channel – of course, the output can be used as the key for one-time pad encryption, but you might as well use it some different way.
For applications beyond that, I am really not an expert, but from what I know, people are looking into a variety of protocols, such as for leader election. There was a review article a few years back by Wehner et al., "Quantum internet: A vision for the road ahead" (https://www.science.org/doi/10.1126/science.aam9288), which highlights some proposals.
As for applications like signing, one aspect to consider is that quantum entanglement will, at least for another decade or two, always be much shorter-lived than classical data at rest. Thus, most practical quantum protocols will boil down to creating and making use of entanglement in a short amount of time, e.g. to initially establish some sort of shared secret, make a coordinated decision, etc.
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.)
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 unreachable by classical means.
This is not wrong, but in my opinion quite misleading. QKD is no replacement for asymmetric cryptography since it requires exchanging a secret key before the communication can take place. This makes it functionally equivalent to a symmetric stream cipher. So why do you mention prime factorization and cite RSA? The security of QKD should be compared to that of the best symmetric algorithms, not that of asymmetric ones.
I have seen this pattern in many talks and papers from the field. Maybe the issue is that the QKD community seems to have almost no overlap with the IT security community. In my experience, QKD people almost never talk about how you would actually use and/or attack a system in practice.
It's not an accident, it's deliberate deception.
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.
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.
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.
A while back, I summarized all the ways I could think of where the layer under QKD fall apart. I think the list is still valid:
https://rdist.root.org/2008/10/24/quantum-cryptography-is-us...
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 convolution and substitution functions, or using hashing to to distribute the information over a very large finite field. The security in quantum appears inseparable from the encoding and implementation itself, which implies there is a proof and description of entropy-in vs. entropy-out that I haven't gone deep enough to locate and read yet.
I'd speculate there would be some interesting unification of the Shannon information entropy of a plaintext with physical state thermodynamic entropy of the "enciphered" Qbits, given transmitting quantum keys like this sounds more like encoding bits into a physical quantum function than a keyed "encryption" scheme for data for the purposes of security.
To do the data exchange, it's not encrypted to a key per se, but it sounds more like a lookup table (LUT) over a field of qbit state probabilities. Doing certification of the security of such a system is different from a normal NIST algorithm candidate because it reads like you could write and evaluate the encoding scheme as a proof.
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?
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.
Popular science articles aren't sufficient to reason about the science - but they are at least as rigorous as the product spec sheets people will make their security decisions on, so I'd propose pop articles are admissable in discussing the security of the scheme. It's not on the consumer to understand, but on the producer to demonstrate.
The issue with QKD right now is that the risk/benefit isn't there from a security product perspective. If I have something that needs quantum security, I necessarily don't trust a bunch of people who say, "trust me, it's science," as I am looking at where the risk goes. If I'm using crypto on classical computers, most of my risk gets diffused through standards bodies (NIST, essentially), and then my vendors, banks, insurers, etc. QKD and PUFs have the same problem, which is snakeoil risk.
The information theoretic security (as a function of entropy) of an algorithm is scientifically interesting, but when it comes to applying it to risk management (e.g. distributing accountability), there is a ceiling on that. Measuring security based on work or operations over a classical compute cost / complexity class, I agree, is an orthogonal concern with QKD, but security as defined by where the risk goes needs a definition it can reason about.
I agree it (the analysis) will look different, and if I were to equip my fellow security analysts with a tool, it would be to not be persuaded that their lack of a quantum physics background disqualifies them from interrogating the real security benefits of QKD proposals.
Also I think the added value of device-independence is overstated. While it does indeed prevent loss of security by faulty quantum hardware (even if constructed maliciously), there is still a lot of classical post-processing required. That device still needs to be trusted. For example, when the device is outputting the shared key, it still needs to be trusted that it isn't also delivering that key back to Eve.
Is checking authenticity needed if you’re communicating with just one party?
From what I understood from the article the data received can be assumed to be random and private between two parties if a high enough win rate is achieved.
Or is checking authenticity to guard against another party taking the entangled particles but not the key used for authenticating?
FYI I don’t have very strong knowledge in this area.
This makes using QKD very hard to justify in practice. If you have exchanged a pre-shared key (which is required for authentication anyway), you can just use a symmetric stream cipher like AES for encrypting the communication. This is many orders of magnitude cheaper and faster than QKD and works independently of the communication medium. Also it doesn't look like AES is going to be broken anytime soon.
Otherwise the standard Person-in-the-Middle attack would apply: Eve (claiming to be Bob) first runs a full protocol session (quantum + classical communication) with Alice, resulting in a shared key X. Then she does the same to Bob, resulting in a key Y. When Alice wants to encrypt a message to Bob, she encrypts with X. Eve can decrypt (and optionally re-encrypt with Y and forward the message to Bob).
> Quantum Theory Demonstrated: Observation Affects Reality
https://www.sciencedaily.com/releases/1998/02/980227055013.h...
Would like to see this applied in a cryptographic system (if it hasn't already been done). The cryptosystem gets destroyed upon observation or an attempt to measure it is in place. Caveat being: the secret(s) gets destroyed upon someone attempting to crack them.
> Strange as it may sound, interference can only occur when no one is watching.
This is not true. The correct statement is that interference only manifest itself in isolated systems, i.e. systems that are not entangled with anything outside of themselves. Systems that are being "measured" or "watched" are entangled, but they are not the only such systems. Any entanglement outside of the system under consideration is enough to stop interference effects from manifesting themselves.
The reason I say "outside of the system under consideration" is because the ability to observe interference depends on where you draw the line between the system you are measuring and everything else. For example, in an EPR pair you can choose to either consider a single member of the pair, in which case you cannot observe any interference, or you can consider the pair as a whole, in which case you can.
The challenge (which the authors don't actually name, and which they take a long time to even describe) is key distribution. Apparently their solution is for Alice and Bob to each have a quantum object that is entangled with the other.
But now they have the same problem, but harder: how to distribute entangled quantum objects.
What have I missed?