Memory attacks on device-independent quantum
Colbeck, Roger
Device-independent quantum cryptographic schemes aim to guarantee security to users based only on the output statistics of any components used, and without the need to verify their internal functionality. Since this would protect users against untrustworthy or incompetent manufacturers, sabotage or device degradation, this idea has excited much interest, and many device-independent schemes have been proposed. Here we identify a critical weakness of device-independent quantum cryptographic protocols that rely on public communication between secure laboratories. Untrusted devices may record their inputs and outputs and reveal information about them via publicly discussed outputs during later runs. Reusing devices thus compromises the security of a protocol and risks leaking secret data. Possible defences include securely destroying or isolating used devices. However, these are costly and often impractical. We briefly consider other possible defences available in scenarios where device reuse is restricted.
 So our next talk is by Roger Koldbeck from ETH. He's going to talk about joint work with Jonathan Barrett and Adrian Kent, memory attacks on device-independent cryptography. Okay, so thanks very much, and it's a great pleasure to be here in Singapore. Yeah, so as Thomas just mentioned, I'm going to talk about memory attacks on device-independent cryptography. So this is work with John Barrett and Adrian Kent, and what we were kind of doing was asking the question, what happens in device-independent cryptography if we think about reusing the devices? So after we've done some cryptographic protocol, we take those devices, remember that we're not trusting them? What happens if we try to reuse them? What are the potential problems that can occur in that situation? And what I'm going to focus on today is what some implications are on some known QKD protocols, and at the end I'll discuss that there are some, or some recent ideas of how to maybe avoid these attacks in certain situations. So as we heard earlier, but I'll just quickly recap, there are in some sense two sides of cryptography. As we all know, that's why we're at this conference. So there's the theoretical side and the practical side. So on the theoretical side, usually we start with some sort of clean, well-defined assumptions and try to use these to prove security. And on the practical side, of course, we want to try to build devices that hopefully satisfy these theoretical assumptions as closely as possible. So in the very first security proofs we came up with, we normally think of some very, let's say, extremely clean assumptions, like we have devices that emit single photons in any state and we can form arbitrary measurements with very, with arbitrarily high fidelity. And of course we go to our experimental friends and they say, look, you must be joking. Actually what we can do is this, and they give some prescription of their devices, and then we go, hmm, okay, well, I guess I have to go and change my assumptions and work on my proof. Okay, so there's this kind of mismatch between the theoretical assumptions that go into a security proof and what the actual devices that we have can actually achieve. Okay, so, and we've seen examples where this can go wrong. These hacking attacks, for example, this one here, and they basically highlight that certain implementations don't satisfy the assumptions of the proof. And so what we would like to do is, of course, base the proof on the weakest assumptions that we can, that we can, and this will mean that the real-life scenario is, of course, closer to satisfying these assumptions. Okay, and this is basically the idea behind device independence. So here we want to make, try to prove security without making any assumptions on the workings of the device. And of course if we could do that, then this mismatch between the assumptions and what happens in practice would be as small as possible. Okay, so when I just sort of say what I mean by device independence, when I use this term, I'm going to be no trust tool in any of the quantum devices used in the protocol. So just to contrast this with some other weaker concepts that have been introduced like semi-device independence where you trust some features such as the dimensions of the systems being used, the results of this talk don't necessarily apply to these weaker forms. So and just to emphasize with device independence, it wouldn't matter if an adversary tampered with or substituted my devices, we would still have security. Okay, so those of you who are at the talks this morning, of course we saw these assumptions being used there. Okay, so about in device independence, we still have to make assumptions. So it's not true that we can just throw away all assumptions. So in particular, so I'm just going to discuss the assumptions that we're still going to keep for the attacks that I described today. And these I think are pretty much necessary assumptions whenever we do cryptography. So here's a sort of schematic of Alice's lab. And the first assumption is that this wall here is a strong wall. So no information can pass through this wall except as Alice desires. So of course there are channels that we need such as here's an insecure quantum channel. So any quantum information sent between Alice and Bob is sent down an insecure quantum channel. Any classical information is sent down an authenticated classical channel. But apart from this Alice knows, apart from receiving these untrusted quantum states, Alice can ensure that nothing else leaks outside her laboratory. Okay, and this is of course extremely important. If I've got an untrusted device, what you may worry about is, well, why doesn't my device just send its information directly to the eavesdropper? Well that's not really in a, I mean the way we think about it, it's not an assumption on the device, but it's an assumption that there are these strong walls that Alice can use to prevent any information, unwanted information leaking. Okay, the other thing, Alice has a trusted private random string. So this is just something that she can use that no one else knows about. And she has a trusted classical computer with which to process information within her own lab. And as well as having this big device, this big laboratory wall here, she can also subpartition her laboratory into subwalls if she wants. If she has two untrusted devices, she can prevent them from communicating with each other by placing them within different regions of her own laboratory. Okay, and Bob also, I haven't drawn this, but his setup is similar. Okay, so what do we know? Well, there are some existing schemes for device independent QKD, and these have been proven to be, and some have even been proven to be unconditionally secure. For example, I mean, there's just a few of them. The first one is Barrett Hardy Kent, then some work by Masane Zittal, Hengie and Rena, and Masane's Pirrone and Asin. These are the most recent ones. Okay, and these protocols here require as many devices as candidates entangled pairs for the proof to go through. So what does that mean? Well, if I go back to this, it basically means we have to have as many devices, Alice has to have as many, all these devices in her lab, they're all within their own little sublab walls and that prevents them communicating from each other. And of course, the hope is that that's just a technical feature of the proof. And in some recent work, these two papers that came out a week ago suggest ways to get around that where you can actually still have unconditional security without needing so many devices. Okay, so, but what we would like, of course, is this small number of devices, and not only that, we would like to be able to reuse those devices. So it's also a bit inconvenient if I have to sort of throw away my devices after I've done my protocol. So what I want to talk about today is the naive reuse of these can lead to supposedly secret data being compromised. Okay, so this is an issue of the composability of the protocol. Of course, we don't only want to, let's say we're talking about a QKD protocol, we don't only want to generate secure key, we also want to be able to use it, for example, as a one-time pad. So there are security definitions that guarantee composable security. However, this is maybe one type of composable security. And there's another type which is, so one type is the thing, is the key I've generated composable in the sense, can I use it in an arbitrary application? The second type of composability is other devices in a sense composable, so can I use the devices in an arbitrary additional application? And of course, the problem is that devices equipped with a memory can remember all their inputs and outputs and can try to leak them if they are reused. Okay, so now I'm going to sort of demonstrate a concrete, I'm going to give a concrete protocol and show exactly how this memory can cause these problems. Okay, so let's just take a QKD protocol of the following form. So this is a very common type of protocol. So first of all, we distribute the states. So here's Alice, here's Bob. They receive some states, let's say they're supplied by Eve. Of course, it doesn't matter that much if one of the parties had supplied them and sent them themselves, but let's just say Eve supplies quantum states into these devices of Alice and Bob. Okay, I didn't draw the lab walls here, but there's this kind of shielding to prevent these devices leaking. Okay, so the states are distributed, then Alice picks, or Alice and Bob both pick random numbers from their trusted random string. They input them into the device and get their outputs. So they have this string of inputs at the end and the string of outputs. Okay, and the case I'm going to consider is where they've only got one device each. So this is always the same device in which they're making their inputs and getting their outputs. Okay, the next step, they publicly announce their measurement choices. So Alice, using this authenticated public channel, tells Bob, look, I measured this. Bob tells her I measured these. Of course, this is potentially overheard by the eavesdropper. Okay, and they check if, I mean, they may have some part of their protocol where they check for suitable numbers of particular input combinations or something like this. Okay, the next thing is parameter estimation. So Alice randomly and independently decides to announce each output bit to Bob, doing so with some probability mu. Okay, and Bob can now use these communicated bits to compute some test function. For example, it could be the average CHSH value of the whole protocol and healer board if it lies outside a specified range. Okay, and then there may still be errors and things in their remaining strings. So they do some kind of error correction and privacy amplification by public discussion. So for example, Alice may, for the privacy amplification step, just tell Bob some hash function to apply to his string and they both apply the same hash function. Okay, so this is a very kind of standard type of protocol. Okay, so let's just suppose that we have a protocol of this type and that it's secure for one use. That means if I run the protocol once, even if I have only one device on each side, it generates a secure key. Okay, and now we're going to consider, well, what happens if we use these same devices to generate another key using the same protocol? Okay, so let's just maybe first think about in what ways can information start to leak. So the first thing is this parameter estimation step. In a sense, you can think of it as a channel from the devices to Eve. Okay, so raw data used for the first key can be leaked while generating the second. So instead of giving honest outputs, if the device tries to instead give some outputs that encode data about the previous key, then this can be leaked if those bits are communicated over the parameter estimation step. Okay, there's also the state distribution step kind of provides a channel from Eve back to the devices, which for example could be used to tell them the error correction and privacy amplification functions used for the first key. Okay, and there's another more subtle channel, which is even whether the protocol aborts or doesn't in some sense, this is provides a channel to Eve. So remember Eve created the devices, that's the sort of assumption. So she could tell them to abort at the right time and such if that if she can do that in such a way that it gives information to her. Okay, so this was just a sort of list of things of ways that Eve can try to exploit it. So for the specific protocol or type of protocol I gave, I can show exactly how that works. So Eve will be able to gain bits of the first key during the generation of a second one. Actually, it's a very simple attack and it can be performed essentially without detection. So first key is just generated correctly, everything happens honestly, the only thing is that the devices remember everything that happened. And now when the second key is generated, what happens is the following. So during the state distribution step of the protocol, Eve uses this to tell the devices the error correction and privacy amplification functions used for the first key. So she was sending, Eve was kind of supplying these states and she also modulates them with some or she tells them this was the privacy amplification function for example and the error correction function that we used when the first key was generated. Okay, so now this device, it knows everything that happened on the first day, it also knows this correction function. So it can now actually compute the final key on the first, it can compute the first key. Okay, so this is now, sounds extremely dangerous because now when we're forming the second key, Alice's device can now substitute certain genuine outputs with bits of the first key. Okay, so for example, it could out, its second output when generating the second key, this is the raw output, it could just be the first bit of the key, the first key. Okay, and now if these are transmitted in the parameter estimation step, they're directly leaked to Eve. So what actually more generally can happen is that Eve can say, I mean we have this parameter mu which is the probability of announcing each step. So if, so Alice, or Eve can program Alice's device to have the first say one over mu outputs be equal to the bit of the first key and then with reasonably large probability, this, one of them gets sent during the parameter estimation phase and if you change one bit of the parameter estimation phase, you won't, I mean the probability of, that won't really affect the abort probability if you're doing something like checking the CHSH, the average CHSH value. Why do you say that Alice's device now can internally compute the raw, the first key? I mean in the first round, the device also calculated the first key, right? I mean, so what you can do is you can, I mean because this device, you can shield it within its own laboratory. Okay, so you mean by device, the inner device, not the whole device, including the computer? Not the computer, no, just the, so it's only the, when I talk about the device, I really mean the quantum device that's being used, the quantum kind of measurement device. Okay, okay. So you should protect, you should shield that such that it doesn't know the private, privacy amplification function necessarily, but this shows that actually it can, can get that anyway. Okay so this was one way that an attack can go and I just picked, I mean this is just to illustrate the idea. So for this specific attack, it's very easy to find a patch, however, I guess the specific attack is not the important thing, but the theoretical point that the current protocols have this weakness. So if you're really proving device independent security of this type of protocol, essentially what you're assuming implicitly somehow is that you're kind of throwing away the devices or never using them again after you've, after one use in order to, to maintain the security. Okay, and there are some other more subtle attacks that are in our paper. We also have some new ideas how to construct secure protocols that get around these in certain restricted scenarios. So when I say restricted scenarios, what I'm really thinking of is alternative notions of composability. So for example, we sort of know that you won't be able to have a universally composable scheme where you reuse the devices because if the scheme is really universally composed by, I can now use the device for anything. And obviously I can't use the device as something to throw out of my laboratory or something like this. So we know that it won't be universally composable, but you can have other notions of composability where say I can reuse my device provided I only ever use it for QKD protocols of the same type, something like this. Okay, so just to conclude, I guess I'm near the end of the time. So these attacks apply to device independent quantum cryptography with no trust of the device is where the devices are reused. So the existing security proofs show that the key is composable, but they don't cover the case where the device is used to generate it are reused. And for all existing schemes, as far as I know, if we try to extend them to two devices, the attacks I presented directly apply. So of course, I don't think this is, I mean, this is not supposed to be the end of device independent cryptography or anything like that. It's just sort of pointing out current weakness of the current schemes. I mean, I still believe that it's a very useful model and a promising way to reduce the assumptions required in cryptography. And I think this work sort of turns over many, many open questions. So I think it sort of suggests that we need new types of protocol and modified notions of composability. And I think that's now the sort of outlook from this work. So let me finish there. Thanks. You have questions for Roger? Oh, thank you. So I think the main lesson is that the hype that we've heard in the past by some people, that device independent could be used literally to allow the eavesdropper to supply the devices might be too strong. But as you just wrote in your outlook, that does not rule out that device independent, if you use device independence to protect against your own ineptitude at building devices and that you're not able to think of all the loopholes that you might have inadvertently left into the machine, then device independent might be a very valid way of doing it. But if you believe that you're doing that so that you would allow the eavesdropper to supply the devices, you might be getting yourself. OK. So it depends a bit on what you want to use the word device independence to mean, of course. So if I try to protect myself against my own incompetence, now I need to have a mathematical model of what my own incompetence is. So I need to characterize how badly I think I might have made my devices. And so to me, that's a bit going away from the device independent idea. I'm sorry, but I don't think that you can be genuinely incompetent to the extent of putting the Trojan horses that... Right. So of course the attack I presented today won't happen by incompetence. That's why I mean yes. But this is not like an exhaustive set of attacks. This is more mental illustration of something that can go wrong. So of course, when we really... I mean really what we want to do, I think, is to come up with a clean, well-defined security model. So if you want your assumption that I'm incompetent but I'm not adversarial, then can you write that down mathematically exactly what that means, that assumption? And if you can, then we can try to prove security from that. So it is conceivable that some of the schemes that have been device independence schemes that have been proven secure are really only secure, really been proven secure against single use and that they could break down even if incompetently manufactured as opposed to adversarial. I think that... They could break down. We just don't know if they are reused. Yes. I think that's conceivable from what the current proofs show. Thank you. We have time for other questions if there are. Do you have an idea of whether some of these measurement device independent schemes would be susceptible to that problem? If you trust some of the devices but not others, would the fact that the untrusted devices could be adversarial and have memory, would that weaken it in the same way? Right. So, I mean, it depends, of course, on scheme by scheme. But let's say you trust your state creation device but not your measurement devices at all. Then, of course, your measurement device can still behave honestly on the first round, remember its inputs and so on and potentially exploit this same attack. I mean, this attack, I mean, it depends exactly on the scheme but let's say if I just have exactly the scheme I presented and I say now I trust my source. I think for the measurement device demand QKD, we do not rely at all on the measurements. When you remember the previous results, it does not matter. You cannot rely on, I mean, what I'm saying is if you take the scheme, the type of scheme I presented, okay, and you replace the state distribution step by a trusted, you assume you trust those states, then the attack still apply. This may not be exactly the same as the scheme you have in mind when you say for measurement device independence. But, I mean, one has to analyze it case by case. So the attacks, if you have another scheme, it doesn't necessarily, the attacks don't necessarily apply but I think there's still something to be proven in general. I'm not sure what did I understand your question. Maybe we can discuss offline. Okay. I think the kind of schemes you're thinking of involve two, Alice and Bob, each have a trusted state preparation device and Eve is the untrusted person. I think there's a good chance that those are having a memory for Eve, doesn't enable her to break it in the way here. As you're thinking of Alice prepares and Bob measures, I think in that case it is susceptible to this attack. Okay. Thanks. Maybe one last question. Okay. If not, let's thank both speakers of the session again. So we now have a half hour coffee break and we reconvene at 3.45.
 So our next talk is by Roger Koldbeck from ETH.  He's going to talk about joint work with Jonathan Barrett and Adrian Kent, memory attacks  on device-independent cryptography.  Okay, so thanks very much, and it's a great pleasure to be here in Singapore.  Yeah, so as Thomas just mentioned, I'm going to talk about memory attacks on device-independent  cryptography.  So this is work with John Barrett and Adrian Kent, and what we were kind of doing was asking  the question, what happens in device-independent cryptography if we think about reusing the  devices?  So after we've done some cryptographic protocol, we take those devices, remember that we're  not trusting them?  What happens if we try to reuse them?  What are the potential problems that can occur in that situation?  And what I'm going to focus on today is what some implications are on some known QKD protocols,  and at the end I'll discuss that there are some, or some recent ideas of how to maybe  avoid these attacks in certain situations.  So as we heard earlier, but I'll just quickly recap, there are in some sense two sides of  cryptography.  As we all know, that's why we're at this conference.  So there's the theoretical side and the practical side.  So on the theoretical side, usually we start with some sort of clean, well-defined assumptions  and try to use these to prove security.  And on the practical side, of course, we want to try to build devices that hopefully satisfy  these theoretical assumptions as closely as possible.  So in the very first security proofs we came up with, we normally think of some very, let's  say, extremely clean assumptions, like we have devices that emit single photons in any  state and we can form arbitrary measurements with very, with arbitrarily high fidelity.  And of course we go to our experimental friends and they say, look, you must be joking.  Actually what we can do is this, and they give some prescription of their devices, and  then we go, hmm, okay, well, I guess I have to go and change my assumptions and work on  my proof.  Okay, so there's this kind of mismatch between the theoretical assumptions that go into a  security proof and what the actual devices that we have can actually achieve.  Okay, so, and we've seen examples where this can go wrong.  These hacking attacks, for example, this one here, and they basically highlight that certain  implementations don't satisfy the assumptions of the proof.  And so what we would like to do is, of course, base the proof on the weakest assumptions  that we can, that we can, and this will mean that the real-life scenario is, of course,  closer to satisfying these assumptions.  Okay, and this is basically the idea behind device independence.  So here we want to make, try to prove security without making any assumptions on the workings  of the device.  And of course if we could do that, then this mismatch between the assumptions and what  happens in practice would be as small as possible.  Okay, so when I just sort of say what I mean by device independence, when I use this term,  I'm going to be no trust tool in any of the quantum devices used in the protocol.  So just to contrast this with some other weaker concepts that have been introduced like semi-device  independence where you trust some features such as the dimensions of the systems being  used, the results of this talk don't necessarily apply to these weaker forms.  So and just to emphasize with device independence, it wouldn't matter if an adversary tampered  with or substituted my devices, we would still have security.  Okay, so those of you who are at the talks this morning, of course we saw these assumptions  being used there.  Okay, so about in device independence, we still have to make assumptions.  So it's not true that we can just throw away all assumptions.  So in particular, so I'm just going to discuss the assumptions that we're still going to  keep for the attacks that I described today.  And these I think are pretty much necessary assumptions whenever we do cryptography.  So here's a sort of schematic of Alice's lab.  And the first assumption is that this wall here is a strong wall.  So no information can pass through this wall except as Alice desires.  So of course there are channels that we need such as here's an insecure quantum channel.  So any quantum information sent between Alice and Bob is sent down an insecure quantum channel.  Any classical information is sent down an authenticated classical channel.  But apart from this Alice knows, apart from receiving these untrusted quantum states, Alice  can ensure that nothing else leaks outside her laboratory.  Okay, and this is of course extremely important.  If I've got an untrusted device, what you may worry about is, well, why doesn't my device  just send its information directly to the eavesdropper?  Well that's not really in a, I mean the way we think about it, it's not an assumption  on the device, but it's an assumption that there are these strong walls that Alice can  use to prevent any information, unwanted information leaking.  Okay, the other thing, Alice has a trusted private random string.  So this is just something that she can use that no one else knows about.  And she has a trusted classical computer with which to process information within her own  lab.  And as well as having this big device, this big laboratory wall here, she can also subpartition  her laboratory into subwalls if she wants.  If she has two untrusted devices, she can prevent them from communicating with each other by  placing them within different regions of her own laboratory.  Okay, and Bob also, I haven't drawn this, but his setup is similar.  Okay, so what do we know?  Well, there are some existing schemes for device independent QKD, and these have been  proven to be, and some have even been proven to be unconditionally secure.  For example, I mean, there's just a few of them.  The first one is Barrett Hardy Kent, then some work by Masane Zittal, Hengie and Rena, and  Masane's Pirrone and Asin.  These are the most recent ones.  Okay, and these protocols here require as many devices as candidates entangled pairs  for the proof to go through.  So what does that mean?  Well, if I go back to this, it basically means we have to have as many devices, Alice has  to have as many, all these devices in her lab, they're all within their own little sublab  walls and that prevents them communicating from each other.  And of course, the hope is that that's just a technical feature of the proof.  And in some recent work, these two papers that came out a week ago suggest ways to get  around that where you can actually still have unconditional security without needing  so many devices.  Okay, so, but what we would like, of course, is this small number of devices, and not only  that, we would like to be able to reuse those devices.  So it's also a bit inconvenient if I have to sort of throw away my devices after I've  done my protocol.  So what I want to talk about today is the naive reuse of these can lead to supposedly  secret data being compromised.  Okay, so this is an issue of the composability of the protocol.  Of course, we don't only want to, let's say we're talking about a QKD protocol, we don't  only want to generate secure key, we also want to be able to use it, for example, as  a one-time pad.  So there are security definitions that guarantee composable security.  However, this is maybe one type of composable security.  And there's another type which is, so one type is the thing, is the key I've generated  composable in the sense, can I use it in an arbitrary application?  The second type of composability is other devices in a sense composable, so can I use  the devices in an arbitrary additional application?  And of course, the problem is that devices equipped with a memory can remember all their  inputs and outputs and can try to leak them if they are reused.  Okay, so now I'm going to sort of demonstrate a concrete, I'm going to give a concrete protocol  and show exactly how this memory can cause these problems.  Okay, so let's just take a QKD protocol of the following form.  So this is a very common type of protocol.  So first of all, we distribute the states.  So here's Alice, here's Bob.  They receive some states, let's say they're supplied by Eve.  Of course, it doesn't matter that much if one of the parties had supplied them and sent  them themselves, but let's just say Eve supplies quantum states into these devices of Alice  and Bob.  Okay, I didn't draw the lab walls here, but there's this kind of shielding to prevent  these devices leaking.  Okay, so the states are distributed, then Alice picks, or Alice and Bob both pick random  numbers from their trusted random string.  They input them into the device and get their outputs.  So they have this string of inputs at the end and the string of outputs.  Okay, and the case I'm going to consider is where they've only got one device each.  So this is always the same device in which they're making their inputs and getting their  outputs.  Okay, the next step, they publicly announce their measurement choices.  So Alice, using this authenticated public channel, tells Bob, look, I measured this.  Bob tells her I measured these.  Of course, this is potentially overheard by the eavesdropper.  Okay, and they check if, I mean, they may have some part of their protocol where they  check for suitable numbers of particular input combinations or something like this.  Okay, the next thing is parameter estimation.  So Alice randomly and independently decides to announce each output bit to Bob, doing  so with some probability mu.  Okay, and Bob can now use these communicated bits to compute some test function.  For example, it could be the average CHSH value of the whole protocol and healer board if  it lies outside a specified range.  Okay, and then there may still be errors and things in their remaining strings.  So they do some kind of error correction and privacy amplification by public discussion.  So for example, Alice may, for the privacy amplification step, just tell Bob some hash  function to apply to his string and they both apply the same hash function.  Okay, so this is a very kind of standard type of protocol.  Okay, so let's just suppose that we have a protocol of this type and that it's secure  for one use.  That means if I run the protocol once, even if I have only one device on each side, it  generates a secure key.  Okay, and now we're going to consider, well, what happens if we use these same devices  to generate another key using the same protocol?  Okay, so let's just maybe first think about in what ways can information start to leak.  So the first thing is this parameter estimation step.  In a sense, you can think of it as a channel from the devices to Eve.  Okay, so raw data used for the first key can be leaked while generating the second.  So instead of giving honest outputs, if the device tries to instead give some outputs  that encode data about the previous key, then this can be leaked if those bits are communicated  over the parameter estimation step.  Okay, there's also the state distribution step kind of provides a channel from Eve  back to the devices, which for example could be used to tell them the error correction  and privacy amplification functions used for the first key.  Okay, and there's another more subtle channel, which is even whether the protocol aborts  or doesn't in some sense, this is provides a channel to Eve.  So remember Eve created the devices, that's the sort of assumption.  So she could tell them to abort at the right time and such if that if she can do that in  such a way that it gives information to her.  Okay, so this was just a sort of list of things of ways that Eve can try to exploit it.  So for the specific protocol or type of protocol I gave, I can show exactly how that works.  So Eve will be able to gain bits of the first key during the generation of a second one.  Actually, it's a very simple attack and it can be performed essentially without detection.  So first key is just generated correctly, everything happens honestly, the only thing  is that the devices remember everything that happened.  And now when the second key is generated, what happens is the following.  So during the state distribution step of the protocol, Eve uses this to tell the devices  the error correction and privacy amplification functions used for the first key.  So she was sending, Eve was kind of supplying these states and she also modulates them with  some or she tells them this was the privacy amplification function for example and the  error correction function that we used when the first key was generated.  Okay, so now this device, it knows everything that happened on the first day, it also knows  this correction function.  So it can now actually compute the final key on the first, it can compute the first key.  Okay, so this is now, sounds extremely dangerous because now when we're forming the second  key, Alice's device can now substitute certain genuine outputs with bits of the first key.  Okay, so for example, it could out, its second output when generating the second key, this  is the raw output, it could just be the first bit of the key, the first key.  Okay, and now if these are transmitted in the parameter estimation step, they're directly  leaked to Eve.  So what actually more generally can happen is that Eve can say, I mean we have this parameter  mu which is the probability of announcing each step.  So if, so Alice, or Eve can program Alice's device to have the first say one over mu outputs  be equal to the bit of the first key and then with reasonably large probability, this, one  of them gets sent during the parameter estimation phase and if you change one bit of the parameter  estimation phase, you won't, I mean the probability of, that won't really affect the abort probability  if you're doing something like checking the CHSH, the average CHSH value.  Why do you say that Alice's device now can internally compute the raw, the first key?  I mean in the first round, the device also calculated the first key, right?  I mean, so what you can do is you can, I mean because this device, you can shield it within  its own laboratory.  Okay, so you mean by device, the inner device, not the whole device, including the computer?  Not the computer, no, just the, so it's only the, when I talk about the device, I really  mean the quantum device that's being used, the quantum kind of measurement device.  Okay, okay.  So you should protect, you should shield that such that it doesn't know the private, privacy  amplification function necessarily, but this shows that actually it can, can get that  anyway.  Okay so this was one way that an attack can go and I just picked, I mean this is just  to illustrate the idea.  So for this specific attack, it's very easy to find a patch, however, I guess the specific  attack is not the important thing, but the theoretical point that the current protocols  have this weakness.  So if you're really proving device independent security of this type of protocol, essentially  what you're assuming implicitly somehow is that you're kind of throwing away the devices  or never using them again after you've, after one use in order to, to maintain the security.  Okay, and there are some other more subtle attacks that are in our paper.  We also have some new ideas how to construct secure protocols that get around these in certain  restricted scenarios.  So when I say restricted scenarios, what I'm really thinking of is alternative notions  of composability.  So for example, we sort of know that you won't be able to have a universally composable scheme  where you reuse the devices because if the scheme is really universally composed by,  I can now use the device for anything.  And obviously I can't use the device as something to throw out of my laboratory or something  like this.  So we know that it won't be universally composable, but you can have other notions of composability  where say I can reuse my device provided I only ever use it for QKD protocols of the  same type, something like this.  Okay, so just to conclude, I guess I'm near the end of the time.  So these attacks apply to device independent quantum cryptography with no trust of the  device is where the devices are reused.  So the existing security proofs show that the key is composable, but they don't cover  the case where the device is used to generate it are reused.  And for all existing schemes, as far as I know, if we try to extend them to two devices,  the attacks I presented directly apply.  So of course, I don't think this is, I mean, this is not supposed to be the end of device  independent cryptography or anything like that.  It's just sort of pointing out current weakness of the current schemes.  I mean, I still believe that it's a very useful model and a promising way to reduce the assumptions  required in cryptography.  And I think this work sort of turns over many, many open questions.  So I think it sort of suggests that we need new types of protocol and modified notions  of composability.  And I think that's now the sort of outlook from this work.  So let me finish there.  Thanks.  You have questions for Roger?  Oh, thank you.  So I think the main lesson is that the hype that we've heard in the past by some people,  that device independent could be used literally to allow the eavesdropper to supply the devices  might be too strong.  But as you just wrote in your outlook, that does not rule out that device independent,  if you use device independence to protect against your own ineptitude at building devices  and that you're not able to think of all the loopholes that you might have inadvertently  left into the machine, then device independent might be a very valid way of doing it.  But if you believe that you're doing that so that you would allow the eavesdropper to  supply the devices, you might be getting yourself.  OK.  So it depends a bit on what you want to use the word device independence to mean, of course.  So if I try to protect myself against my own incompetence, now I need to have a mathematical  model of what my own incompetence is.  So I need to characterize how badly I think I might have made my devices.  And so to me, that's a bit going away from the device independent idea.  I'm sorry, but I don't think that you can be genuinely incompetent to the extent of  putting the Trojan horses that...  Right.  So of course the attack I presented today won't happen by incompetence.  That's why I mean yes.  But this is not like an exhaustive set of attacks.  This is more mental illustration of something that can go wrong.  So of course, when we really... I mean really what we want to do, I think, is to come up  with a clean, well-defined security model.  So if you want your assumption that I'm incompetent but I'm not adversarial, then can you write  that down mathematically exactly what that means, that assumption?  And if you can, then we can try to prove security from that.  So it is conceivable that some of the schemes that have been device independence schemes  that have been proven secure are really only secure, really been proven secure against  single use and that they could break down even if incompetently manufactured as opposed  to adversarial.  I think that...  They could break down.  We just don't know if they are reused.  Yes.  I think that's conceivable from what the current proofs show.  Thank you.  We have time for other questions if there are.  Do you have an idea of whether some of these measurement device independent schemes would  be susceptible to that problem?  If you trust some of the devices but not others, would the fact that the untrusted devices could  be adversarial and have memory, would that weaken it in the same way?  Right.  So, I mean, it depends, of course, on scheme by scheme.  But let's say you trust your state creation device but not your measurement devices at  all.  Then, of course, your measurement device can still behave honestly on the first round,  remember its inputs and so on and potentially exploit this same attack.  I mean, this attack, I mean, it depends exactly on the scheme but let's say if I just have  exactly the scheme I presented and I say now I trust my source.  I think for the measurement device demand QKD, we do not rely at all on the measurements.  When you remember the previous results, it does not matter.  You cannot rely on, I mean, what I'm saying is if you take the scheme, the type of scheme  I presented, okay, and you replace the state distribution step by a trusted, you assume  you trust those states, then the attack still apply.  This may not be exactly the same as the scheme you have in mind when you say for measurement  device independence.  But, I mean, one has to analyze it case by case.  So the attacks, if you have another scheme, it doesn't necessarily, the attacks don't  necessarily apply but I think there's still something to be proven in general.  I'm not sure what did I understand your question.  Maybe we can discuss offline.  Okay.  I think the kind of schemes you're thinking of involve two, Alice and Bob, each have a  trusted state preparation device and Eve is the untrusted person.  I think there's a good chance that those are having a memory for Eve, doesn't enable her  to break it in the way here.  As you're thinking of Alice prepares and Bob measures, I think in that case it is susceptible  to this attack.  Okay.  Thanks.  Maybe one last question.  Okay.  If not, let's thank both speakers of the session again.  So we now have a half hour coffee break and we reconvene at 3.45.
Memory_attacks_on_device-independent_quantum_0_1775.png Memory_attacks_on_device-independent_quantum_1776_1895.png Memory_attacks_on_device-independent_quantum_1896_2027.png Memory_attacks_on_device-independent_quantum_2028_2135.png Memory_attacks_on_device-independent_quantum_2136_2303.png Memory_attacks_on_device-independent_quantum_2304_6383.png Memory_attacks_on_device-independent_quantum_6384_7835.png Memory_attacks_on_device-independent_quantum_7836_8039.png Memory_attacks_on_device-independent_quantum_8040_9419.png Memory_attacks_on_device-independent_quantum_9420_13307.png Memory_attacks_on_device-independent_quantum_13308_16151.png Memory_attacks_on_device-independent_quantum_16152_21623.png Memory_attacks_on_device-independent_quantum_21624_26231.png Memory_attacks_on_device-independent_quantum_26232_26759.png Memory_attacks_on_device-independent_quantum_26760_26951.png Memory_attacks_on_device-independent_quantum_26952_28979.png Memory_attacks_on_device-independent_quantum_28980_32927.png Memory_attacks_on_device-independent_quantum_32928_34415.png Memory_attacks_on_device-independent_quantum_34416_34907.png Memory_attacks_on_device-independent_quantum_34908_35507.png Memory_attacks_on_device-independent_quantum_35508_36299.png Memory_attacks_on_device-independent_quantum_36300_36383.png Memory_attacks_on_device-independent_quantum_36384_37259.png Memory_attacks_on_device-independent_quantum_37260_37526.png
So our next talk is by Roger Koldbeck from ETH. He's going to talk about joint work with Jonathan Barrett and Adrian Kent, memory attacks on device-independent cryptography. Okay, so thanks very much, and it's a great pleasure to be here in Singapore. Yeah, so as Thomas just mentioned, I'm going to talk about memory attacks on device-independent cryptography. So this is work with John Barrett and Adrian Kent, and what we were kind of doing was asking the question, what happens in device-independent cryptography if we think about reusing the devices? So after we've done some cryptographic protocol, we take those devices, remember that we're not trusting them? What happens if we try to reuse them? What are the potential problems that can occur in that situation? And what I'm going to focus on today is what some implications are on some known QKD protocols, and at the end I'll discuss that there are some, or some recent ideas of how to maybe avoid these attacks in certain situations. So as we heard earlier, but I'll just quickly recap, there are in some sense two sides of cryptography. As we all know, that's why we're at this conference. So there's the theoretical side and the practical side. So on the theoretical side, usually we start with some sort of clean, well-defined assumptions and try to use these to prove security. And on the practical side, of course, we want to try to build devices that hopefully satisfy these theoretical assumptions as closely as possible. So in the very first security proofs we came up with, we normally think of some very, let's say, extremely clean assumptions, like we have devices that emit single photons in any state and we can form arbitrary measurements with very, with arbitrarily high fidelity. And of course we go to our experimental friends and they say, look, you must be joking. Actually what we can do is this, and they give some prescription of their devices, and then we go, hmm, okay, well, I guess I have to go and change my assumptions and work on my proof. Okay, so there's this kind of mismatch between the theoretical assumptions that go into a security proof and what the actual devices that we have can actually achieve. Okay, so, and we've seen examples where this can go wrong. These hacking attacks, for example, this one here, and they basically highlight that certain implementations don't satisfy the assumptions of the proof. And so what we would like to do is, of course, base the proof on the weakest assumptions that we can, that we can, and this will mean that the real-life scenario is, of course, closer to satisfying these assumptions. Okay, and this is basically the idea behind device independence. So here we want to make, try to prove security without making any assumptions on the workings of the device. And of course if we could do that, then this mismatch between the assumptions and what happens in practice would be as small as possible. Okay, so when I just sort of say what I mean by device independence, when I use this term, I'm going to be no trust tool in any of the quantum devices used in the protocol. So just to contrast this with some other weaker concepts that have been introduced like semi-device independence where you trust some features such as the dimensions of the systems being used, the results of this talk don't necessarily apply to these weaker forms. So and just to emphasize with device independence, it wouldn't matter if an adversary tampered with or substituted my devices, we would still have security. Okay, so those of you who are at the talks this morning, of course we saw these assumptions being used there. Okay, so about in device independence, we still have to make assumptions. So it's not true that we can just throw away all assumptions. So in particular, so I'm just going to discuss the assumptions that we're still going to keep for the attacks that I described today. And these I think are pretty much necessary assumptions whenever we do cryptography. So here's a sort of schematic of Alice's lab. And the first assumption is that this wall here is a strong wall. So no information can pass through this wall except as Alice desires. So of course there are channels that we need such as here's an insecure quantum channel. So any quantum information sent between Alice and Bob is sent down an insecure quantum channel. Any classical information is sent down an authenticated classical channel. But apart from this Alice knows, apart from receiving these untrusted quantum states, Alice can ensure that nothing else leaks outside her laboratory. Okay, and this is of course extremely important. If I've got an untrusted device, what you may worry about is, well, why doesn't my device just send its information directly to the eavesdropper? Well that's not really in a, I mean the way we think about it, it's not an assumption on the device, but it's an assumption that there are these strong walls that Alice can use to prevent any information, unwanted information leaking. Okay, the other thing, Alice has a trusted private random string. So this is just something that she can use that no one else knows about. And she has a trusted classical computer with which to process information within her own lab. And as well as having this big device, this big laboratory wall here, she can also subpartition her laboratory into subwalls if she wants. If she has two untrusted devices, she can prevent them from communicating with each other by placing them within different regions of her own laboratory. Okay, and Bob also, I haven't drawn this, but his setup is similar. Okay, so what do we know? Well, there are some existing schemes for device independent QKD, and these have been proven to be, and some have even been proven to be unconditionally secure. For example, I mean, there's just a few of them. The first one is Barrett Hardy Kent, then some work by Masane Zittal, Hengie and Rena, and Masane's Pirrone and Asin. These are the most recent ones. Okay, and these protocols here require as many devices as candidates entangled pairs for the proof to go through. So what does that mean? Well, if I go back to this, it basically means we have to have as many devices, Alice has to have as many, all these devices in her lab, they're all within their own little sublab walls and that prevents them communicating from each other. And of course, the hope is that that's just a technical feature of the proof. And in some recent work, these two papers that came out a week ago suggest ways to get around that where you can actually still have unconditional security without needing so many devices. Okay, so, but what we would like, of course, is this small number of devices, and not only that, we would like to be able to reuse those devices. So it's also a bit inconvenient if I have to sort of throw away my devices after I've done my protocol. So what I want to talk about today is the naive reuse of these can lead to supposedly secret data being compromised. Okay, so this is an issue of the composability of the protocol. Of course, we don't only want to, let's say we're talking about a QKD protocol, we don't only want to generate secure key, we also want to be able to use it, for example, as a one-time pad. So there are security definitions that guarantee composable security. However, this is maybe one type of composable security. And there's another type which is, so one type is the thing, is the key I've generated composable in the sense, can I use it in an arbitrary application? The second type of composability is other devices in a sense composable, so can I use the devices in an arbitrary additional application? And of course, the problem is that devices equipped with a memory can remember all their inputs and outputs and can try to leak them if they are reused. Okay, so now I'm going to sort of demonstrate a concrete, I'm going to give a concrete protocol and show exactly how this memory can cause these problems. Okay, so let's just take a QKD protocol of the following form. So this is a very common type of protocol. So first of all, we distribute the states. So here's Alice, here's Bob. They receive some states, let's say they're supplied by Eve. Of course, it doesn't matter that much if one of the parties had supplied them and sent them themselves, but let's just say Eve supplies quantum states into these devices of Alice and Bob. Okay, I didn't draw the lab walls here, but there's this kind of shielding to prevent these devices leaking. Okay, so the states are distributed, then Alice picks, or Alice and Bob both pick random numbers from their trusted random string. They input them into the device and get their outputs. So they have this string of inputs at the end and the string of outputs. Okay, and the case I'm going to consider is where they've only got one device each. So this is always the same device in which they're making their inputs and getting their outputs. Okay, the next step, they publicly announce their measurement choices. So Alice, using this authenticated public channel, tells Bob, look, I measured this. Bob tells her I measured these. Of course, this is potentially overheard by the eavesdropper. Okay, and they check if, I mean, they may have some part of their protocol where they check for suitable numbers of particular input combinations or something like this. Okay, the next thing is parameter estimation. So Alice randomly and independently decides to announce each output bit to Bob, doing so with some probability mu. Okay, and Bob can now use these communicated bits to compute some test function. For example, it could be the average CHSH value of the whole protocol and healer board if it lies outside a specified range. Okay, and then there may still be errors and things in their remaining strings. So they do some kind of error correction and privacy amplification by public discussion. So for example, Alice may, for the privacy amplification step, just tell Bob some hash function to apply to his string and they both apply the same hash function. Okay, so this is a very kind of standard type of protocol. Okay, so let's just suppose that we have a protocol of this type and that it's secure for one use. That means if I run the protocol once, even if I have only one device on each side, it generates a secure key. Okay, and now we're going to consider, well, what happens if we use these same devices to generate another key using the same protocol? Okay, so let's just maybe first think about in what ways can information start to leak. So the first thing is this parameter estimation step. In a sense, you can think of it as a channel from the devices to Eve. Okay, so raw data used for the first key can be leaked while generating the second. So instead of giving honest outputs, if the device tries to instead give some outputs that encode data about the previous key, then this can be leaked if those bits are communicated over the parameter estimation step. Okay, there's also the state distribution step kind of provides a channel from Eve back to the devices, which for example could be used to tell them the error correction and privacy amplification functions used for the first key. Okay, and there's another more subtle channel, which is even whether the protocol aborts or doesn't in some sense, this is provides a channel to Eve. So remember Eve created the devices, that's the sort of assumption. So she could tell them to abort at the right time and such if that if she can do that in such a way that it gives information to her. Okay, so this was just a sort of list of things of ways that Eve can try to exploit it. So for the specific protocol or type of protocol I gave, I can show exactly how that works. So Eve will be able to gain bits of the first key during the generation of a second one. Actually, it's a very simple attack and it can be performed essentially without detection. So first key is just generated correctly, everything happens honestly, the only thing is that the devices remember everything that happened. And now when the second key is generated, what happens is the following. So during the state distribution step of the protocol, Eve uses this to tell the devices the error correction and privacy amplification functions used for the first key. So she was sending, Eve was kind of supplying these states and she also modulates them with some or she tells them this was the privacy amplification function for example and the error correction function that we used when the first key was generated. Okay, so now this device, it knows everything that happened on the first day, it also knows this correction function. So it can now actually compute the final key on the first, it can compute the first key. Okay, so this is now, sounds extremely dangerous because now when we're forming the second key, Alice's device can now substitute certain genuine outputs with bits of the first key. Okay, so for example, it could out, its second output when generating the second key, this is the raw output, it could just be the first bit of the key, the first key. Okay, and now if these are transmitted in the parameter estimation step, they're directly leaked to Eve. So what actually more generally can happen is that Eve can say, I mean we have this parameter mu which is the probability of announcing each step. So if, so Alice, or Eve can program Alice's device to have the first say one over mu outputs be equal to the bit of the first key and then with reasonably large probability, this, one of them gets sent during the parameter estimation phase and if you change one bit of the parameter estimation phase, you won't, I mean the probability of, that won't really affect the abort probability if you're doing something like checking the CHSH, the average CHSH value. Why do you say that Alice's device now can internally compute the raw, the first key? I mean in the first round, the device also calculated the first key, right? I mean, so what you can do is you can, I mean because this device, you can shield it within its own laboratory. Okay, so you mean by device, the inner device, not the whole device, including the computer? Not the computer, no, just the, so it's only the, when I talk about the device, I really mean the quantum device that's being used, the quantum kind of measurement device. Okay, okay. So you should protect, you should shield that such that it doesn't know the private, privacy amplification function necessarily, but this shows that actually it can, can get that anyway. Okay so this was one way that an attack can go and I just picked, I mean this is just to illustrate the idea. So for this specific attack, it's very easy to find a patch, however, I guess the specific attack is not the important thing, but the theoretical point that the current protocols have this weakness. So if you're really proving device independent security of this type of protocol, essentially what you're assuming implicitly somehow is that you're kind of throwing away the devices or never using them again after you've, after one use in order to, to maintain the security. Okay, and there are some other more subtle attacks that are in our paper. We also have some new ideas how to construct secure protocols that get around these in certain restricted scenarios. So when I say restricted scenarios, what I'm really thinking of is alternative notions of composability. So for example, we sort of know that you won't be able to have a universally composable scheme where you reuse the devices because if the scheme is really universally composed by, I can now use the device for anything. And obviously I can't use the device as something to throw out of my laboratory or something like this. So we know that it won't be universally composable, but you can have other notions of composability where say I can reuse my device provided I only ever use it for QKD protocols of the same type, something like this. Okay, so just to conclude, I guess I'm near the end of the time. So these attacks apply to device independent quantum cryptography with no trust of the device is where the devices are reused. So the existing security proofs show that the key is composable, but they don't cover the case where the device is used to generate it are reused. And for all existing schemes, as far as I know, if we try to extend them to two devices, the attacks I presented directly apply. So of course, I don't think this is, I mean, this is not supposed to be the end of device independent cryptography or anything like that. It's just sort of pointing out current weakness of the current schemes. I mean, I still believe that it's a very useful model and a promising way to reduce the assumptions required in cryptography. And I think this work sort of turns over many, many open questions. So I think it sort of suggests that we need new types of protocol and modified notions of composability. And I think that's now the sort of outlook from this work. So let me finish there. Thanks. You have questions for Roger? Oh, thank you. So I think the main lesson is that the hype that we've heard in the past by some people, that device independent could be used literally to allow the eavesdropper to supply the devices might be too strong. But as you just wrote in your outlook, that does not rule out that device independent, if you use device independence to protect against your own ineptitude at building devices and that you're not able to think of all the loopholes that you might have inadvertently left into the machine, then device independent might be a very valid way of doing it. But if you believe that you're doing that so that you would allow the eavesdropper to supply the devices, you might be getting yourself. OK. So it depends a bit on what you want to use the word device independence to mean, of course. So if I try to protect myself against my own incompetence, now I need to have a mathematical model of what my own incompetence is. So I need to characterize how badly I think I might have made my devices. And so to me, that's a bit going away from the device independent idea. I'm sorry, but I don't think that you can be genuinely incompetent to the extent of putting the Trojan horses that... Right. So of course the attack I presented today won't happen by incompetence. That's why I mean yes. But this is not like an exhaustive set of attacks. This is more mental illustration of something that can go wrong. So of course, when we really... I mean really what we want to do, I think, is to come up with a clean, well-defined security model. So if you want your assumption that I'm incompetent but I'm not adversarial, then can you write that down mathematically exactly what that means, that assumption? And if you can, then we can try to prove security from that. So it is conceivable that some of the schemes that have been device independence schemes that have been proven secure are really only secure, really been proven secure against single use and that they could break down even if incompetently manufactured as opposed to adversarial. I think that... They could break down. We just don't know if they are reused. Yes. I think that's conceivable from what the current proofs show. Thank you. We have time for other questions if there are. Do you have an idea of whether some of these measurement device independent schemes would be susceptible to that problem? If you trust some of the devices but not others, would the fact that the untrusted devices could be adversarial and have memory, would that weaken it in the same way? Right. So, I mean, it depends, of course, on scheme by scheme. But let's say you trust your state creation device but not your measurement devices at all. Then, of course, your measurement device can still behave honestly on the first round, remember its inputs and so on and potentially exploit this same attack. I mean, this attack, I mean, it depends exactly on the scheme but let's say if I just have exactly the scheme I presented and I say now I trust my source. I think for the measurement device demand QKD, we do not rely at all on the measurements. When you remember the previous results, it does not matter. You cannot rely on, I mean, what I'm saying is if you take the scheme, the type of scheme I presented, okay, and you replace the state distribution step by a trusted, you assume you trust those states, then the attack still apply. This may not be exactly the same as the scheme you have in mind when you say for measurement device independence. But, I mean, one has to analyze it case by case. So the attacks, if you have another scheme, it doesn't necessarily, the attacks don't necessarily apply but I think there's still something to be proven in general. I'm not sure what did I understand your question. Maybe we can discuss offline. Okay. I think the kind of schemes you're thinking of involve two, Alice and Bob, each have a trusted state preparation device and Eve is the untrusted person. I think there's a good chance that those are having a memory for Eve, doesn't enable her to break it in the way here. As you're thinking of Alice prepares and Bob measures, I think in that case it is susceptible to this attack. Okay. Thanks. Maybe one last question. Okay. If not, let's thank both speakers of the session again. So we now have a half hour coffee break and we reconvene at 3.45.
device-independent cryptography. Okay, so thanks without making any assumptions on the workings of possible. Okay, so when I just sort of say what I quantum devices used in the protocol. So just to information sent between Alice and Bob is sent untrusted device, what you may worry about is, information, unwanted information leaking. Okay, the other thing, Alice has a trusted private so many devices. Okay, so, but what we would these can lead to supposedly secret data being security definitions that guarantee composable security. However, this is maybe one type of memory can remember all their inputs and outputs them gets sent during the parameter estimation independent security of this type of protocol, protocols that get around these in certain restricted scenarios. So when I say restricted notions of composability where say I can reuse my the end of device independent cryptography or out current weakness of the current schemes. I need new types of protocol and modified notions schemes that have been proven secure are really only secure, really been proven secure against