Weak String Erasure

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.

Tags: Specific Task, Two Party Protocols, weak string erasure,Building Blocks, Bounded Storage Mode [4]

Assumptions

• We assume that the adversary has access to a quantum memory that is bounded in size, say the memory is of at most $\log _{2}(d)$ qubits. See Bounded/Noisy Storage Model in [4]/[3]
• 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.

Outline

Alice and Bob first agree on a duration Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta t} 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. 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 $\Delta t$. 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.
  

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

• • $n$ the total number of rounds.
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1^n} denotes the string Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1,\ldots,A_n} .
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} denotes the Hadamard gate. $H^{0}=I$ and $H^{1}=H$
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1^n} is the random string Alice sends to Bob by the WSE protocol.
  • $\Theta _{i}$ encodes Alice's choice of basis in round $i$.
  • ${\hat {X}}_{1}^{n}$ is Bob's outcomes measurement.
  • ${\hat {\Theta }}_{i}$ encodes Bob's choice of basis in round $i$.
  • $M$ denotes dishonest Bob quantum memory, that can store a state of dimension at most $d$.
  • $\Delta t$ is a duration during which both parties will wait.
  • $\epsilon >0$ is a security parameter.
  • ${\mathcal {I}}$ denotes the set of rounds where Alice and Bob have chosen the same basis.
  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_\mathcal{I}} denotes the sub-string of $A_{1}^{n}$ whose bit are in ${\mathcal {I}}$.
• Let us define the following function.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma(x):= \begin{cases} x, & \text{ if } x>1/2 \\ g^{-1}(x), & \text{ if } x\leq 1/2 \end{cases} }
where $g(x):=h(x)+x-1$, and $h(x):=-x\log(x)-(1-x)\log(1-x)$.

Requirements

• Network Stage: Prepare and Measure.
• Relevant Network Parameters: $\epsilon _{T}$ , $\epsilon _{M}$ (see Prepare and Measure Network Stage)
• The parties need a random number generator.

Properties

• If (dishonest) Bob holds a quantum memory of dimension at most $d$, then his (smooth) min-entropy is lower bounded as follows,
  

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_{\min}^\epsilon(X_1^n | K \Theta_1^n M) \geq n \gamma\left(\frac{-\log_2(d)}{n}\right) -1- \log_2\frac{2}{\epsilon^2},}
where $K$ is any classical information Bob can hold, and $M$ represents Bob's quantum state in his memory. This quantum state has dimension at most $d$.

• Alice is ignorant about the set ${\mathcal {I}}$, the set of rounds in which Alice and Bob have chosen the same basis.

See (WSE?) for precise definition.

Protocol Description

Inputs: n
Output: $X_{1}^{n}$, ${\mathcal {I}}$, $X_{\mathcal {I}}$.

1. Alice and Bob agree on a time $\Delta t$.
2. For $i$ in $[n]$ do:
   1. Alice chooses uniformly at random $\Theta _{i}\in \{0,1\}$ and $X_{i}\in \{0,1\}$.
   2. Alice prepares the state $H^{\Theta _{i}}|X_{i}\rangle$. She sends it over to Bob.
   3. Bob announces receiving a state.
   4. Bob chooses uniformly at random ${\hat {\Theta }}_{i}\in \{0,1\}$.
   5. Bob measures the incoming qubit in the standard basis if ${\hat {\Theta }}_{i}=0$ and in the Hadamard basis otherwise. He gets outcome ${\hat {X}}_{i}$

1. At this stage Alice has string $X_{1}^{n}$ and $\Theta _{1}^{n}$, and Bob has strings ${\hat {X}}_{1}^{n}$ and ${\hat {\Theta }}_{1}^{n}$.
2. Alice and Bob wait for time Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta t} .
3. Alice sends $\Theta _{1}^{n}$ to Bob.
4. Bob computes ${\mathcal {I}}:=\{i\in [n]:\Theta _{i}={\hat {\Theta }}_{i}\}$.
5. Bob erases all bits from ${\hat {X}}_{1}^{n}$ with index $i\notin {\mathcal {I}}$. Bob holds string ${\hat {X}}_{\mathcal {I}}$, and we should have $X_{\mathcal {I}}={\hat {X}}_{\mathcal {I}}$.

Further Information

• The Bounded Storage Model was introduced in [5], [4]
• The Bounded Storage Model can be generalised into the Noisy Storage Models [3], [1]
• The security of Weak String Erasure has been analyzed in the presence of noise and losses [2]

References

1. KWW (2012)
2. WCSL (2010)
3. WST (2008)
4. Schaffner(2007)
5. DFSS (2005)

contributed by Jérémy Ribeiro