A min-entropy uncertainty relation for finite size cryptography
CC Attribution - NonCommercial - NoDerivatives 2.5 Switzerland:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Ng, Nelly
Apart from their foundational signicance, entropic uncertainty relations play a central role in proving the security of quantum cryptographic protocols. Of particular interest are thereby relations in terms of the smooth min-entropy for BB84 and six-state encodings. Previously, strong uncertainty relations were obtained which are valid in the limit of large block lengths. Here, we prove a new uncertainty relation in terms of the smooth min-entropy that is only marginally less strong, but has the crucial property that it can be applied to rather small block lengths. This paves the way for a practical implementation of many cryptographic protocols. As part of our proof we show tight uncertainty relations for a family of Renyi entropies that may be of independent interest.
 Good afternoon. It's a pleasure to be here. I hope you have enjoyed the conference. So I'm a student at Security Working with Stephanie. And today I will share a bit about a new Meet entropy uncertainty relation that we have worked on. This is joint work with Mario from EtH. So I guess before delving into the uncertainty relation, I would like to motivate our findings by sharing with you where we started out from. So I will first talk a bit about two party problems as we're seeing in Christian's talk. And then we introduced the noise storage model and I will discuss the role of these Meet entropy uncertainty relations in this model. Then I will present our results for a new bound on the Meet entropy uncertainty relation. And then I will discuss how did we apply this to an experimental bit commitment here at the security. So throughout this conference we have been seeing a lot of discussions about how to do, how to perform secure communication. And conventionally, one of the main goals is to protect the players from an unauthorized party, an eavesdropper. And we have also heard many interesting discussions about QKD where you have unconditional security. But I guess there are also a large class of other cryptographic problems, like for example, secure function evaluation where Christian has just introduced us to. And in these protocols, we don't have eave. We don't have any eavesdropper on the protocol. But Alice and Bob however do not trust each other. So the security requirements then transform into saying that if a party is honest, then he is protected from a possibly cheating party in this protocol. So for a quick example, let's maybe just look at the case where Alice has a tractor and she wants to sell it for 5,000 euros or higher. And Bob is on a limited budget, so he wants to get the tractor. But then both parties have some sort of requirements. So Alice wants to get the highest price as possible. And Bob, well, he doesn't really want Alice to know how much money he has. Like in case she's not sincere in selling the truck, she's just curious about how much money he has. And then this would imply a secure function evaluation where it outputs no if Bob's budget is not enough and it just outputs Bob's price otherwise. So these protocols have a very fundamental, can be built by a few building blocks that we know as big commitment and oblivious transfer. So in classical cryptography, these things can only be done with assumptions. So there was initial optimism that maybe quantum cryptography can provide better solutions. But of course, as we've seen, there are many impossible proofs that have proved the contrary. As Christian had said that Lowell and Chowell and also independently mayors have proved that quantum big commitment is impossible and also Lowell proved that one sided two party computations are impossible. And now we have from Christian that two sided are also impossible. So the extension of proofs for, impossibility proofs for big commitment also show at the most generalized big commitment protocols. If one party is secure, then the other party can always cheat with a very large probability which is impractical in some sense. So however, security still arises if we are willing to bound the quantum capabilities of an adversary. So I think that these assumptions are much stronger than classical assumptions simply because quantum information is considerably harder to manipulate compared to classical information. So there have been some general assumptions, for example that an attacker cannot perform end coherent measurements and also by including the relativistic special relativity theory like the talks that have been given by Adrian and Jed on Tuesday. Also, if it's long known that if we have a bounded, the adversary has a bounded quantum storage, then security might in principle be available. So suppose now that we have a single copy of a quantum state and we want to store it for some time delta t and later retrieve it. So with current technology, this is extremely hard and basically the noisy storage model just dates the central assumption that the quantum memory available for an adversary is bounded and subjected to noise. So and also this, it's also important to note that this assumption is still compatible with increasing advancements in quantum memories because if you have a fixed assumption of how much storage you have, you can simply acquire security still by sending a larger state to the adversary. So security in this model arises from this quantum protocol called the weak string erasure, which is actually a very simple protocol. You can think of it as a black box which provides Alice with n-length binary string and Bob with a random subset of this string. So this can be done by the following. At some initial time t, Alice will choose a random binary string and she prepares it by encoding each qubit in the random BB84 basis and she sends the state to Bob. So an honest Bob will measure also randomly in the BB84 basis and then produce the measurement results. And after some time delta t, Alice will announce her basis information to Bob and he will pick out those where the basis coincide. So the security for this protocol for Alice would mean that Bob cannot learn the whole string that she has, which we quantify by saying that the epsilon smooth min entropy is greater than some value. So security for Bob would mean that Alice does not learn about his subset, which means that Alice basically doesn't learn about his basis. Also note that it is clear that how the noisy storage assumption comes in. So if Bob here had unlimited and perfect quantum storage, he could easily store everything that Alice provides him and only measure after she announces her basis. So with this week's string erasure protocol, if we combine it with some other classical information processing, we can achieve fundamental secure two-party protocols such as bid commitment and uplift transfer. So let us consider how do we quantify the uncertainty of Bob, the uncertainty of Bob with this string of X and that Alice possesses. So suppose that he receives the state from Alice, he can then perform some arbitrary classical measurement on part of the state and then encode the rest into quantum information and store it for some time where his noisy storage is subjected to some noise until Alice reveals her basis. So then the uncertainty will be quantified by this amount of min entropy conditioned on these three informations that Bob possesses and this is in principle the negative logarithm of the probability that Bob guesses the string correctly except with some small probability of failure. So the name problem left is to find optimal bounds for this quantity such that we can make the min entropy per bit large enough. So it's also important to make this quantity as large as possible because if we want to give a robust version of Wich string erasure against experimental errors, the uncertainty is actually a resource for us. So there are two main challenges in looking at these uncertainty relations. The first one is to consider further consider these relations for quantum site information. We can for example link this to the classical capacity of the quantum memory and also for example the entanglement cost. So there has been work done for partial work done for the quantum by linking this to the quantum capacity of quantum memory but this is only done for six states instead of BB84 measurements. Also another issue that arises for this uncertainty relations is that finite size effects are usually quite apparent and they also happen in QKD. So similarly there has been some work that analyzes these effects for QKD. So our approach in deriving the uncertainty relations is quite conventional. So we first derive the uncertainty relation by conditioning on classical information only then we link it to the classical capacity of these quantum memories. The reason to do that is because well this approach is much better understood and also for that there are a large range of quantum channels which obey the strong converse so we can easily link this to the classical capacity instead of the quantum capacity. So if we return to the weak string erasure scenario where Alice prepares BB84 states and sends them to Bob who measures this is in principle done by Alice creating entangled photon pass and she measures one of them while sending the other half to Bob. So this is due to the non-signalling properties of this process this is actually equivalent to Bob first measuring the state and by doing so he effectively will prepare a state which is labelled with some classical information K here and then Alice measures this state by random BB84 bases. So the scenario here would describe our weak string erasure and the problem is what is the mean entropy about Bob's total information about this string of length n. So Thunkat and Sergifere and these other people have established this relation that says that it is not too far away from the Shannon entropy this is the result that they have. Well so the first thing to notice is that the error parameter that the smoothing parameter will decrease exponentially with n however this decrease is this convergence is kind of slow so for small choices of this epsilon and the factor that describes the amount away from the Shannon entropy for small choices we can deduce from this expression that we need a very large number of qubits for this relation to be good enough for an implementation purpose. So our approach to this problem lies on the crucial idea that we extend this proof by linking the alpha conditional entropies instead of just the Shannon entropy by give it to give a bound on the epsilon smooth mean entropy. So for our new results we can have a significant lower amount for m for the same amount of mean entropy rate and the similarly tied relations can also be obtained for six-state measurements. So I will give a brief description of what we proved and if you're interested you can read the paper which is on archive. So we first start with a single qubit uncertainty relation and what we did was we performed a theoretical minimization over all single qubit states for these conditional alpha-renier entropies. So the way to do this is to rewrite these alpha entropies into spherical coordinates then we invoke the Bloch sphere condition for any arbitrary qubit sorry and then we will obtain this quantity. So this can be generalized into for an n qubit state by showing that this minimum amount will increase linearly with n and then at the third step what we did is we further conditioned this on the classical information that Bob has. So note that we show that this the relation that we have in the third step it actually coincides with the second step because well in our scenario Bob prepares the state and he knows the classical information where Alice despite whatever classical information Bob holds she will measure with the BB84 basis randomly. So the probability distribution of Zeta Alice's basis and the classical information that Bob has are independent of each other and finally the last step is to link this to the mean entropy the smooth mean entropy quantity which we use which we did by using the relations that Marko, Roger and Renato they developed and then we arrive at our final result. So this result which is conditioned on Alice's basis and the classical information that Bob has can be extended to including quantum site information by considering the classical capacity of Bob's quantum memory. So this is a graph which shows the difference between our results and the previous uncertainty relation for different amounts of mean entropy rate. So we can see here that for same amounts of mean entropy rate we can achieve the same amount with a considerably smaller number of n which means the finite size effects do not hit us so hard here. So for an application of this we use the relation in the implementation of bit commitment in the noisy storage model and for security in this experiment that we did we needed the absolute mean smooth mean entropy to be very large. So this happens for two reasons. The first reason is that we need to make the protocol robust against the experimental errors and the second reason is to minimize the amount of classical post processing information that we need by also considering the errors that occur due to finite size effects. So it would be almost infeasible if we were to invoke the old relation but by using this relation we can do this and we have performed the bit commitment by using 250,000 qubits in the Wichering Erasure which is this is a robust version against experimental errors and losses. So I will conclude by saying that our relation is particularly useful for Wichering Erasure. So and Wichering Erasure can be used to construct new protocols in the noisy storage model. So I guess this pays away to actually implementing these relations and for our work on the bit commitment protocol we have done a secure commitment with execution error, a small execution error by assuming a quantum storage of around 900 qubits which I think is a quite strong assumption. So other interesting problems to look at in the future would to be constructing new protocols that use us the Wichering Erasure and also it will be interesting in general to see if we can obtain these relations for quantum site information so that we can prove security for Wichering Erasure for even larger range of quantum channels. So with this I will end my presentation. Thank you. Thank you. Okay thank you very much. So we have time for a few questions. Any reason why in the experiment you chose that particular figure to bound your memory or just sorry. So you choose some particular number there to bound your memory to analyze the experiment. So this one? Not later you say. I mean so of course this experiment cannot be conclusive if you don't assume some bounded storage. Yes. There you assume some 920 something. Yes. So what does this number come from? It's just something you... So what we did was we fixed the amount of qubits we need to send in the protocol and we fixed the security error and by performing the security proof we showed that if we have lower... If Bob's quantum memory is smaller than that amount then the protocol will be secure. He will never... In essence he will never be... He will not be able to break the protocol. So if you assume even a smaller amount let's say 100 then you can exchange more bits. I can exchange more. Or you can get more security or whatever the figure of merities. Well... I mean if there is no memory in the extreme case there is no memory at all then... Well of course because we still need to consider that the fact that experimenters errors occur would mean that Alice will have to send additional information which decreases the amount of uncertainty that Bob has. So this is kind of an optimal result to commit to commit a bit and in that experiment we necessarily need to send that much qubits. Let's thank Meli again.
 Good afternoon. It's a pleasure to be here. I hope you have enjoyed the conference.  So I'm a student at Security Working with Stephanie.  And today I will share a bit about a new Meet entropy uncertainty relation that we have worked on.  This is joint work with Mario from EtH.  So I guess before delving into the uncertainty relation, I would like to motivate our findings by  sharing with you where we started out from. So I will first talk a bit about two party problems  as we're seeing in Christian's talk. And then we introduced the noise storage model and I will  discuss the role of these Meet entropy uncertainty relations in this model. Then I will present our  results for a new bound on the Meet entropy uncertainty relation. And then I will discuss  how did we apply this to an experimental bit commitment here at the security.  So throughout this conference we have been seeing a lot of discussions about how to do,  how to perform secure communication. And conventionally, one of the main goals is to protect  the players from an unauthorized party, an eavesdropper. And we have also heard many interesting  discussions about QKD where you have unconditional security. But I guess there are also a large  class of other cryptographic problems, like for example, secure function evaluation where  Christian has just introduced us to. And in these protocols, we don't have eave. We don't have any  eavesdropper on the protocol. But Alice and Bob however do not trust each other. So the security  requirements then transform into saying that if a party is honest, then he is protected from a  possibly cheating party in this protocol. So for a quick example, let's maybe just look at  the case where Alice has a tractor and she wants to sell it for 5,000 euros or higher. And Bob is  on a limited budget, so he wants to get the tractor. But then both parties have some sort of  requirements. So Alice wants to get the highest price as possible. And Bob, well, he doesn't  really want Alice to know how much money he has. Like in case she's not sincere in selling the  truck, she's just curious about how much money he has. And then this would imply a secure function  evaluation where it outputs no if Bob's budget is not enough and it just outputs Bob's price  otherwise. So these protocols have a very fundamental, can be built by a few building blocks  that we know as big commitment and oblivious transfer. So in classical cryptography, these things  can only be done with assumptions. So there was initial optimism that maybe quantum cryptography  can provide better solutions. But of course, as we've seen, there are many impossible proofs  that have proved the contrary. As Christian had said that Lowell and Chowell and also independently  mayors have proved that quantum big commitment is impossible and also Lowell proved that one  sided two party computations are impossible. And now we have from Christian that two sided  are also impossible. So the extension of proofs for, impossibility proofs for big commitment  also show at the most generalized big commitment protocols. If one party is secure,  then the other party can always cheat with a very large probability which is impractical in some  sense. So however, security still arises if we are willing to bound the quantum capabilities of  an adversary. So I think that these assumptions are much stronger than classical assumptions  simply because quantum information is considerably harder to manipulate compared to classical  information. So there have been some general assumptions, for example that an attacker cannot  perform end coherent measurements and also by including the relativistic special relativity  theory like the talks that have been given by Adrian and Jed on Tuesday. Also, if it's long  known that if we have a bounded, the adversary has a bounded quantum storage, then security might  in principle be available. So suppose now that we have a single copy of a quantum state and we  want to store it for some time delta t and later retrieve it. So with current technology, this is  extremely hard and basically the noisy storage model just dates the central assumption that  the quantum memory available for an adversary is bounded and subjected to noise. So and also  this, it's also important to note that this assumption is still compatible with increasing  advancements in quantum memories because if you have a fixed assumption of how much storage you  have, you can simply acquire security still by sending a larger state to the adversary.  So security in this model arises from this quantum protocol called the weak string erasure,  which is actually a very simple protocol. You can think of it as a black box which provides Alice  with n-length binary string and Bob with a random subset of this string. So this can be done by the  following. At some initial time t, Alice will choose a random binary string and she prepares it  by encoding each qubit in the random BB84 basis and she sends the state to Bob. So an honest Bob  will measure also randomly in the BB84 basis and then produce the measurement results. And after  some time delta t, Alice will announce her basis information to Bob and he will pick out those  where the basis coincide. So the security for this protocol for Alice would mean that Bob cannot  learn the whole string that she has, which we quantify by saying that the epsilon smooth min  entropy is greater than some value. So security for Bob would mean that Alice does not learn about  his subset, which means that Alice basically doesn't learn about his basis. Also note that it is  clear that how the noisy storage assumption comes in. So if Bob here had unlimited and perfect quantum  storage, he could easily store everything that Alice provides him and only measure after she  announces her basis. So with this week's string erasure protocol, if we combine it with some other  classical information processing, we can achieve fundamental secure two-party protocols such as  bid commitment and uplift transfer. So let us consider how do we quantify the uncertainty of  Bob, the uncertainty of Bob with this string of X and that Alice possesses. So suppose that he  receives the state from Alice, he can then perform some arbitrary classical measurement  on part of the state and then encode the rest into quantum information and store it for some time  where his noisy storage is subjected to some noise until Alice reveals her basis. So then the  uncertainty will be quantified by this amount of min entropy conditioned on these three  informations that Bob possesses and this is in principle the negative logarithm of the probability  that Bob guesses the string correctly except with some small probability of failure. So the name  problem left is to find optimal bounds for this quantity such that we can make the min entropy  per bit large enough. So it's also important to make this quantity as large as possible because  if we want to give a robust version of Wich string erasure against experimental errors,  the uncertainty is actually a resource for us. So there are two main challenges in looking at  these uncertainty relations. The first one is to consider further consider these relations for  quantum site information. We can for example link this to the classical capacity of the quantum  memory and also for example the entanglement cost. So there has been work done for partial work done  for the quantum by linking this to the quantum capacity of quantum memory but this is only done  for six states instead of BB84 measurements. Also another issue that arises for this uncertainty  relations is that finite size effects are usually quite apparent and they also happen in QKD. So  similarly there has been some work that analyzes these effects for QKD. So our approach in deriving  the uncertainty relations is quite conventional. So we first derive the uncertainty relation  by conditioning on classical information only then we link it to the classical capacity of  these quantum memories. The reason to do that is because well this approach is much better  understood and also for that there are a large range of quantum channels which obey the strong  converse so we can easily link this to the classical capacity instead of the quantum capacity.  So if we return to the weak string erasure scenario where Alice prepares BB84 states  and sends them to Bob who measures this is in principle done by Alice creating entangled  photon pass and she measures one of them while sending the other half to Bob. So this is due to  the non-signalling properties of this process this is actually equivalent to Bob first measuring  the state and by doing so he effectively will prepare a state which is labelled with some classical  information K here and then Alice measures this state by random BB84 bases. So the scenario here  would describe our weak string erasure and the problem is what is the mean entropy about  Bob's total information about this string of length n. So Thunkat and Sergifere and these other people  have established this relation that says that it is not too far away from the Shannon entropy  this is the result that they have. Well so the first thing to notice is that the error parameter  that the smoothing parameter will decrease exponentially with n however this decrease is  this convergence is kind of slow so for small choices of this epsilon and the factor that  describes the amount away from the Shannon entropy for small choices we can deduce from this  expression that we need a very large number of qubits for this relation to be good enough  for an implementation purpose. So our approach to this problem lies on the crucial idea that we  extend this proof by linking the alpha conditional entropies instead of just the Shannon entropy  by give it to give a bound on the epsilon smooth mean entropy. So for our new results  we can have a significant lower amount for m for the same amount of mean entropy rate and  the similarly tied relations can also be obtained for six-state measurements. So I will give a brief  description of what we proved and if you're interested you can read the paper which is on  archive. So we first start with a single qubit uncertainty relation and what we did was we  performed a theoretical minimization over all single qubit states for these conditional  alpha-renier entropies. So the way to do this is to rewrite these alpha entropies into spherical  coordinates then we invoke the Bloch sphere condition for any arbitrary qubit sorry  and then we will obtain this quantity. So this can be generalized into for an n qubit state by  showing that this minimum amount will increase linearly with n and then at the third step what  we did is we further conditioned this on the classical information that Bob has. So note that  we show that this the relation that we have in the third step it actually coincides with the  second step because well in our scenario Bob prepares the state and he knows the classical  information where Alice despite whatever classical information Bob holds she will measure with the  BB84 basis randomly. So the probability distribution of Zeta Alice's basis and the classical information  that Bob has are independent of each other and finally the last step is to link this to the  mean entropy the smooth mean entropy quantity which we use which we did by using the relations that  Marko, Roger and Renato they developed and then we arrive at our final result. So this result  which is conditioned on Alice's basis and the classical information that Bob has can be extended  to including quantum site information by considering the classical capacity of Bob's quantum memory.  So this is a graph which shows the difference between our results and the previous uncertainty  relation for different amounts of mean entropy rate. So we can see here that for same amounts  of mean entropy rate we can achieve the same amount with a considerably smaller number of n which  means the finite size effects do not hit us so hard here. So for an application of this we use the  relation in the implementation of bit commitment in the noisy storage model and for security in  this experiment that we did we needed the absolute mean smooth mean entropy to be very large. So this  happens for two reasons. The first reason is that we need to make the protocol robust against the  experimental errors and the second reason is to minimize the amount of classical post processing  information that we need by also considering the errors that occur due to finite size effects.  So it would be almost infeasible if we were to invoke the old relation but by using this relation  we can do this and we have performed the bit commitment by using 250,000 qubits in the Wichering  Erasure which is this is a robust version against experimental errors and losses.  So I will conclude by saying that our relation is particularly useful for Wichering Erasure. So  and Wichering Erasure can be used to construct new protocols in the noisy storage model. So I guess  this pays away to actually implementing these relations and for our work on the bit commitment  protocol we have done a secure commitment with execution error, a small execution error by assuming  a quantum storage of around 900 qubits which I think is a quite strong assumption. So other  interesting problems to look at in the future would to be constructing new protocols that  use us the Wichering Erasure and also it will be interesting in general to see if we can obtain  these relations for quantum site information so that we can prove security for Wichering Erasure  for even larger range of quantum channels. So with this I will end my presentation. Thank you.  Thank you. Okay thank you very much. So we have time for a few questions.  Any reason why in the experiment you chose that particular figure to bound your memory or just  sorry. So you choose some particular number there to bound your memory to analyze the experiment.  So this one? Not later you say. I mean so of course this experiment cannot be  conclusive if you don't assume some bounded storage. Yes. There you assume some 920 something.  Yes. So what does this number come from? It's just something you... So what we did was we fixed the  amount of qubits we need to send in the protocol and we fixed the security error and by performing  the security proof we showed that if we have lower... If Bob's quantum memory is smaller than that  amount then the protocol will be secure. He will never... In essence he will never be... He will  not be able to break the protocol. So if you assume even a smaller amount let's say 100 then you can  exchange more bits. I can exchange more. Or you can get more security or whatever the figure of  merities. Well... I mean if there is no memory in the extreme case there is no memory at all then...  Well of course because we still need to consider that the fact that experimenters  errors occur would mean that Alice will have to send additional information which  decreases the amount of uncertainty that Bob has. So this is kind of an optimal result to commit  to commit a bit and in that experiment we necessarily need to send that much qubits.  Let's thank Meli again.
A_min-entropy_uncertainty_relation_for_finite_size_cryptography_0_1391.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_1392_4067.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_4068_6275.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_6276_11459.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_11460_11591.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_11592_14687.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_14688_17243.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_17244_20951.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_20952_21179.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_21180_22259.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_22260_24623.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_24624_26531.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_26532_28103.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_28104_29723.png A_min-entropy_uncertainty_relation_for_finite_size_cryptography_29724_29843.png