Write, autoreview, editor, reviewer
3,125
edits
Weak String Erasure: Difference between revisions
m
no edit summary
mNo edit summary |
|||
| Line 1: | Line 1: | ||
Weak String Erasure (WSE) is a two-party functionality, say between Alice and Bob, that allows Alice to send a random bit string to Bob, in such a way that Alice is | Weak String Erasure (WSE) is a two-party functionality, say between Alice and Bob, that allows Alice to send a random bit string to Bob, in such a way that Alice is guaranteed that a fraction (ideally half) of the bits are lost during the transmission. However, Alice should not know which bits Bob has received, and which bits have been lost.</br></br> | ||
'''Tags:''' [[:Category:Specific Task|Specific Task]][[Category:Specific Task]], | '''Tags:''' [[:Category:Specific Task|Specific Task]][[Category:Specific Task]], | ||
[[:Category: Two Party Protocols|Two Party Protocols]] [[Category: Two Party Protocols]], weak string erasure, [[Category: Building Blocks]][[:Category: Building Blocks|Building Blocks]], Bounded Storage Mode [[Weak String Erasure#Further Information| [4]]] | [[:Category: Two Party Protocols|Two Party Protocols]] [[Category: Two Party Protocols]], weak string erasure, [[Category: Building Blocks]][[:Category: Building Blocks|Building Blocks]], Bounded Storage Mode [[Weak String Erasure#Further Information| [4]]] | ||
| Line 6: | Line 6: | ||
*We assume that the adversary has access to a quantum memory that is bounded in size, say the memory is of at most <math>\log_2(d)</math> qubits. See Bounded/Noisy Storage Model in [[Weak String Erasure#References| | *We assume that the adversary has access to a quantum memory that is bounded in size, say the memory is of at most <math>\log_2(d)</math> qubits. See Bounded/Noisy Storage Model in [[Weak String Erasure#References| | ||
[4]/[3] ]] | [4]/[3] ]] | ||
* The transmission of | * The transmission of the qubits is noiseless/lossless. | ||
* The preparation devices (for quantum state) are assumed to be fully characterized and trusted. We assume the same for the measurement devices. | * The preparation devices (for quantum state) are assumed to be fully characterized and trusted. We assume the same for the measurement devices. | ||
==Outline== | ==Outline== | ||
Alice and Bob first agree on a duration <math>\Delta t</math> that should correspond to an estimation of the time needed to make any known quantum memory decoheres. The protocol can be decomposed into three parts. | Alice and Bob first agree on a duration <math>\Delta t</math> that should correspond to an estimation of the time needed to make any known quantum memory decoheres. The protocol can be decomposed into three parts. | ||
*'''Distribution''' This step involves preparation, exchange and measurement of quantum states. Alice chooses a random basis among the X or Z bases. She then chooses at random one of the two states of this basis, prepares this state and sends it over to Bob. Upon receiving the state from Alice, Bob will choose a random basis among the X or Z bases, and measure the incoming qubit in this basis. They both record the basis they have used | *'''Distribution''' This step involves preparation, exchange, and measurement of quantum states. Alice chooses a random basis among the X or Z bases. She then chooses at random one of the two states of this basis, prepares this state and sends it over to Bob. Upon receiving the state from Alice, Bob will choose a random basis among the X or Z bases, and measure the incoming qubit in this basis. They both record the basis they have used. Bob records his measurement outcome and Alice records which state she has sent. Both parties repeat this procedure n times. | ||
*'''Waiting time''' Both parties will wait for time <math>\Delta t</math>. This is to force a malicious party to store part his quantum state in his memory. Of course he will be limited by the size of his quantum memory. | *'''Waiting time''' Both parties will wait for time <math>\Delta t</math>. This is to force a malicious party to store part his quantum state in his memory. Of course, he will be limited by the size of his quantum memory. | ||
* '''Classical post-processing''' Alice will send to Bob, the bases she has used to prepare her states. Bob will erase all the measurement outcomes of the rounds where he measured in a different basis than Alice has prepared the state.</br> | * '''Classical post-processing''' Alice will send to Bob, the bases she has used to prepare her states. Bob will erase all the measurement outcomes of the rounds where he measured in a different basis than Alice has prepared the state.</br> | ||
The losses in the transmission happen in the distribution step when Bob | The losses in the transmission happen in the distribution step when Bob measures the incoming qubit in a different basis than the one Alice has chosen for the preparation. | ||
==Notation== | ==Notation== | ||
| Line 69: | Line 69: | ||
==Further Information== | ==Further Information== | ||
* The Bounded Storage Model was introduced in [[Weak String Erasure#References|[5], [4] ]] | * The Bounded Storage Model was introduced in [[Weak String Erasure#References|[5], [4] ]] | ||
* The Bounded Storage Model can | * The Bounded Storage Model can be generalised into the Noisy Storage Models [[Weak String Erasure#References|[3], [1] ]] | ||
* The security of Weak String Erasure has been analyzed in the presence of noise and losses [[Weak String Erasure#References|[2] ]] | * The security of Weak String Erasure has been analyzed in the presence of noise and losses [[Weak String Erasure#References|[2] ]] | ||
==References== | ==References== | ||