8 ms·

Cryptographers achieve perfect secrecy with imperfect devices

101 points by theafh 5y ago

eiejejr 5y ago
WallyFunk 5y ago
Worth reading this: > Quantum Theory Demonstrated: Observation Affects Reality https://www.sciencedaily.com/releases/1998/02/980227055013.htm 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.
- lisper 5y ago
  This article is very misleading, which is typical of QM material of this era (early 90s). > 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.
NoKnowledge 5y ago
The article suggests that quantum key distribution (QKD) is a replacement for a courier, but that is not true. Distributing an initial small secret key (which allows authenticity of the post-processing of the quantum measurements) is still required. 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.
- mikeiz404 5y ago
  > The article suggests that quantum key distribution (QKD) is a replacement for a courier, but that is not true. Distributing an initial small secret key (which allows authenticity of the post-processing of the quantum measurements) is still required. 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.
  - fsh 5y ago
    Without authentication, any form of communication is susceptible to a man-in-the-middle attack. You simply don't know who you are communicating with. 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.
    - mikeiz404 5y ago
      I made a reply to a similar sibling comment over here https://news.ycombinator.com/item?id=30561845 https://news.ycombinator.com/item?id=30561845
  - NoKnowledge 5y ago
    Yes, otherwise how would you know you are indeed communicating with that party? 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).
motohagiography 5y ago
> 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 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.
- Moodles 5y ago
  > 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?
  - CodesInChaos 5y ago
    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.
- klickverbot 5y ago
klickverbot 5y ago
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 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!
- lanstin 5y ago
  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?
  - klickverbot 5y ago
    > I always read perfect secrecy as a term of art with some technical meaning. 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 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.
cryptonector 5y ago
If there's a non-political topic that HN should consider banning, it's QKD. It has been, is, and will continue to be crypto snake-oil.
NateLawson 5y ago
QKD relies on many underlying assumptions, which researchers conveniently sweep under the rug while continuing to build castles ever higher on the theoretically "perfect" but insecure foundation. It is unclear how the underlying implementation for QKD can be made as secure as modern silicon countermeasures are against attacks like fault injection. 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-useless/ https://rdist.root.org/2008/10/24/quantum-cryptography-is-us...
m3kw9 5y ago
Is this a how to distribute a OTP using quantum mechanics?
- klickverbot 5y ago
  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.
denton-scratch 5y ago
I don't get this. 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?

101 points by theafh 5y ago

Worth reading this: > Quantum Theory Demonstrated: Observation Affects Reality https://www.sciencedaily.com/releases/1998/02/980227055013.htm 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.

lisper 5y ago
This article is very misleading, which is typical of QM material of this era (early 90s). > 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.

NoKnowledge 5y ago

The article suggests that quantum key distribution (QKD) is a replacement for a courier, but that is not true. Distributing an initial small secret key (which allows authenticity of the post-processing of the quantum measurements) is still required. 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.

mikeiz404 5y ago
> The article suggests that quantum key distribution (QKD) is a replacement for a courier, but that is not true. Distributing an initial small secret key (which allows authenticity of the post-processing of the quantum measurements) is still required. 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.
- fsh 5y ago
  Without authentication, any form of communication is susceptible to a man-in-the-middle attack. You simply don't know who you are communicating with. 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.
  - mikeiz404 5y ago
    I made a reply to a similar sibling comment over here https://news.ycombinator.com/item?id=30561845 https://news.ycombinator.com/item?id=30561845
- NoKnowledge 5y ago
  Yes, otherwise how would you know you are indeed communicating with that party? 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).

motohagiography 5y ago

> 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 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.

Moodles 5y ago
> 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?
- CodesInChaos 5y ago
  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.
klickverbot 5y ago

klickverbot 5y ago

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 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!

lanstin 5y ago
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?
- klickverbot 5y ago
  > I always read perfect secrecy as a term of art with some technical meaning. 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 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.

cryptonector 5y ago

If there's a non-political topic that HN should consider banning, it's QKD. It has been, is, and will continue to be crypto snake-oil.

NateLawson 5y ago

QKD relies on many underlying assumptions, which researchers conveniently sweep under the rug while continuing to build castles ever higher on the theoretically "perfect" but insecure foundation. It is unclear how the underlying implementation for QKD can be made as secure as modern silicon countermeasures are against attacks like fault injection. 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-useless/ https://rdist.root.org/2008/10/24/quantum-cryptography-is-us...

m3kw9 5y ago

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

klickverbot 5y ago
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.

denton-scratch 5y ago

I don't get this. 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?