Revision History for: Prepare-and-Measure Weak String Erasure
- 2025-06-24 at 21:56 by JuliaM
implements Weak String Erasure
Introduction
This protocol implements Weak String Erasure (WSE) in a prepare-and-measure setup. This is often used as a subroutine in other protocols.
Outline
Alice and Bob first agree on a duration $\\\Delta_t$ that should correspond to an estimation of the time needed to make any known quantum memory decohere. 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 of their quantum state in their 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 on a different basis than Alice 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.
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] and [3]
- The transmission of the qubits is noiseless/lossless.
- The preparation devices (for quantum states) are assumed to be fully characterized and trusted. We assume the same for the measurement devices.
Requirements
Network Stage: Prepare and Measure.
Relevant Network Parameters: $\\\epsilon _{T}, \\\epsilon _{M}$ ( These distances are diamond norm distances between the states obtained from ideal quantum channels, measurement and real (noisy) quantum channels and measurement.)
The parties need a random number generator.
Notation
- $n$ be the total number of rounds.
- $A_1^n$ denotes the string $A_1, \\\ldots, A_n$.
- $H$ denotes the Hadamard gate. $H^0 = I$ and $H^1 = H$.
- $X_1^n$ is the random string Alice sends to Bob via the WSE protocol.
- $\\\Theta_i$ encodes Alice’s choice of basis in round $i$.
- $\\\hat{X}_1^n$ is Bob’s measurement outcomes.
- $\\\hat{\\\Theta}_i$ encodes Bob’s choice of basis in round $i$.
- $M$ denotes dishonest Bob’s quantum memory, which can store a state of dimension at most $d$.
- $\\\Delta t$ is the 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.
- $A_{\\\mathcal{I}}$ denotes the substring of $A_1^n$ whose bits are in $\\\mathcal{I}$.
Let us define the following function:
$$
\\\gamma(x) :=
\\\begin{cases}
x, & \\\text{if } x > \\\frac{1}{2} \\\\\\\\\
g^{-1}(x), & \\\text{if } x \\\leq \\\frac{1}{2}
\\\end{cases}
$$where
$$
g(x) := h(x) + x – 1, \\\quad \\\text{and} \\\quad h(x) := -x\\\log(x) – (1-x)\\\log(1-x)
$$Properties
- If (dishonest) Bob holds a quantum memory of dimension at most $d$, then his (smooth) min-entropy is lower bounded as follows:
$$ H_{\\\min}^{\\\epsilon}(X_1^n \\\mid K \\\Theta_1^n M) \\\geq n\\\gamma\\\left( \\\frac{-\\\log_2(d)}{n} \\\right) – 1 – \\\log_2\\\left( \\\frac{2}{\\\epsilon^2} \\\right), $$
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 Weak String Erasure for the definition.
Technical Description
Inputs: $n$
Output: $X_1^n$, $\\\mathcal{I}$, $X_{\\\mathcal{I}}$- Alice and Bob agree on a time $\\\Delta t$.
- For $i \\\in [n]$ do:
- Alice chooses uniformly at random $\\\Theta_i \\\in \\\{0,1\\\}$ and $X_i \\\in \\\{0,1\\\}$.
- Alice prepares the state $H^{\\\Theta_i}\\\lvert X_i \\\rangle$. She sends it over to Bob.
- Bob announces receiving a state.
- Bob chooses uniformly at random $\\\hat{\\\Theta}_i \\\in \\\{0,1\\\}$.
- 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$.
- 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$.
- Alice and Bob wait for time $\\\Delta t$.
- Alice sends $\\\Theta_1^n$ to Bob.
- Bob computes $\\\mathcal{I} := \\\{i \\\in [n] : \\\Theta_i = \\\hat{\\\Theta}_i\\\}$.
- 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}}$.
Experimental Implementations
No content has been added to this section, yet!
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 analysed in the presence of noise and losses [2]
References
- Konig, Robert, Stephanie Wehner, and Jürg Wullschleger. “Unconditional security from noisy quantum storage.” IEEE Transactions on Information Theory 58, no. 3 (2012): 1962-1984.
- Wehner, Stephanie, Marcos Curty, Christian Schaffner, and Hoi-Kwong Lo. “Implementation of two-party protocols in the noisy-storage model.” Physical Review A—Atomic, Molecular, and Optical Physics 81, no. 5 (2010): 052336.
- Wehner, Stephanie, Christian Schaffner, and Barbara M. Terhal. “Cryptography from noisy storage.” Physical Review Letters 100, no. 22 (2008): 220502.
- Schaffner, Christian. “Cryptography in the bounded-quantum-storage model.” arXiv preprint arXiv:0709.0289 (2007).
- Damgård, Ivan B., Serge Fehr, Louis Salvail, and Christian Schaffner. “Cryptography in the bounded-quantum-storage model.” SIAM Journal on Computing 37, no. 6 (2008): 1865-1890.
- 2025-05-16 at 18:38 by JuliaM
implements Weak String Erasure
Introduction
This protocol implements Weak String Erasure (WSE) in a prepare-and-measure setup. This is often used as a subroutine in other protocols.
Outline
Alice and Bob first agree on a duration $\\\Delta_t$ that should correspond to an estimation of the time needed to make any known quantum memory decohere. 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 of their quantum state in their 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 on a different basis than Alice 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.
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] and [3]
- The transmission of the qubits is noiseless/lossless.
- The preparation devices (for quantum states) are assumed to be fully characterized and trusted. We assume the same for the measurement devices.
Requirements
Network Stage: Prepare and Measure.
Relevant Network Parameters: $\\\epsilon _{T}, \\\epsilon _{M}$ ( These distances are diamond norm distances between the states obtained from ideal quantum channels, measurement and real (noisy) quantum channels and measurement.)
The parties need a random number generator.
Notation
- $n$ be the total number of rounds.
- $A_1^n$ denotes the string $A_1, \\\ldots, A_n$.
- $H$ denotes the Hadamard gate. $H^0 = I$ and $H^1 = H$.
- $X_1^n$ is the random string Alice sends to Bob via the WSE protocol.
- $\\\Theta_i$ encodes Alice’s choice of basis in round $i$.
- $\\\hat{X}_1^n$ is Bob’s measurement outcomes.
- $\\\hat{\\\Theta}_i$ encodes Bob’s choice of basis in round $i$.
- $M$ denotes dishonest Bob’s quantum memory, which can store a state of dimension at most $d$.
- $\\\Delta t$ is the 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.
- $A_{\\\mathcal{I}}$ denotes the substring of $A_1^n$ whose bits are in $\\\mathcal{I}$.
Let us define the following function:
$$
\\\gamma(x) :=
\\\begin{cases}
x, & \\\text{if } x > \\\frac{1}{2} \\\\\\\\\
g^{-1}(x), & \\\text{if } x \\\leq \\\frac{1}{2}
\\\end{cases}
$$where
$$
g(x) := h(x) + x – 1, \\\quad \\\text{and} \\\quad h(x) := -x\\\log(x) – (1-x)\\\log(1-x)
$$Properties
- If (dishonest) Bob holds a quantum memory of dimension at most $d$, then his (smooth) min-entropy is lower bounded as follows:
$$ H_{\\\min}^{\\\epsilon}(X_1^n \\\mid K \\\Theta_1^n M) \\\geq n\\\gamma\\\left( \\\frac{-\\\log_2(d)}{n} \\\right) – 1 – \\\log_2\\\left( \\\frac{2}{\\\epsilon^2} \\\right), $$
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 Weak String Erasure for the definition.
Technical Description
Inputs: $n$
Output: $X_1^n$, $\\\mathcal{I}$, $X_{\\\mathcal{I}}$- Alice and Bob agree on a time $\\\Delta t$.
- For $i \\\in [n]$ do:
- Alice chooses uniformly at random $\\\Theta_i \\\in \\\{0,1\\\}$ and $X_i \\\in \\\{0,1\\\}$.
- Alice prepares the state $H^{\\\Theta_i}\\\lvert X_i \\\rangle$. She sends it over to Bob.
- Bob announces receiving a state.
- Bob chooses uniformly at random $\\\hat{\\\Theta}_i \\\in \\\{0,1\\\}$.
- 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$.
- 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$.
- Alice and Bob wait for time $\\\Delta t$.
- Alice sends $\\\Theta_1^n$ to Bob.
- Bob computes $\\\mathcal{I} := \\\{i \\\in [n] : \\\Theta_i = \\\hat{\\\Theta}_i\\\}$.
- 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}}$.
Experimental Implementations
No content has been added to this section, yet!
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 analysed in the presence of noise and losses [2]
References
- Konig, Robert, Stephanie Wehner, and Jürg Wullschleger. “Unconditional security from noisy quantum storage.” IEEE Transactions on Information Theory 58, no. 3 (2012): 1962-1984.
- Wehner, Stephanie, Marcos Curty, Christian Schaffner, and Hoi-Kwong Lo. “Implementation of two-party protocols in the noisy-storage model.” Physical Review A—Atomic, Molecular, and Optical Physics 81, no. 5 (2010): 052336.
- Wehner, Stephanie, Christian Schaffner, and Barbara M. Terhal. “Cryptography from noisy storage.” Physical Review Letters 100, no. 22 (2008): 220502.
- Schaffner, Christian. “Cryptography in the bounded-quantum-storage model.” arXiv preprint arXiv:0709.0289 (2007).
- Damgård, Ivan B., Serge Fehr, Louis Salvail, and Christian Schaffner. “Cryptography in the bounded-quantum-storage model.” SIAM Journal on Computing 37, no. 6 (2008): 1865-1890.
- 2025-05-16 at 14:42 by Mina Doosti
implements Weak String Erasure
Introduction
This protocol implements Weak String Erasure (WSE) in a prepare-and-measure setup. This is often used as a subroutine in other protocols.
Outline
Alice and Bob first agree on a duration $Delta_t$ that should correspond to an estimation of the time needed to make any known quantum memory decohere. 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 of their quantum state in their 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 on a different basis than Alice 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.
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] and [3]
- The transmission of the qubits is noiseless/lossless.
- The preparation devices (for quantum states) are assumed to be fully characterized and trusted. We assume the same for the measurement devices.
Requirements
Network Stage: Prepare and Measure.
Relevant Network Parameters: $epsilon _{T}, epsilon _{M}$ ( These distances are diamond norm distances between the states obtained from ideal quantum channels, measurement and real (noisy) quantum channels and measurement.)
The parties need a random number generator.
Notation
- $n$ be the total number of rounds.
- $A_1^n$ denotes the string $A_1, ldots, A_n$.
- $H$ denotes the Hadamard gate. $H^0 = I$ and $H^1 = H$.
- $X_1^n$ is the random string Alice sends to Bob via the WSE protocol.
- $Theta_i$ encodes Alice’s choice of basis in round $i$.
- $hat{X}_1^n$ is Bob’s measurement outcomes.
- $hat{Theta}_i$ encodes Bob’s choice of basis in round $i$.
- $M$ denotes dishonest Bob’s quantum memory, which can store a state of dimension at most $d$.
- $Delta t$ is the 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.
- $A_{mathcal{I}}$ denotes the substring of $A_1^n$ whose bits are in $mathcal{I}$.
Let us define the following function:
$$
gamma(x) :=
begin{cases}
x, & text{if } x > frac{1}{2} \\\\\\\\\
g^{-1}(x), & text{if } x leq frac{1}{2}
end{cases}
$$where
$$
g(x) := h(x) + x – 1, quad text{and} quad h(x) := -xlog(x) – (1-x)log(1-x)
$$Properties
- If (dishonest) Bob holds a quantum memory of dimension at most $d$, then his (smooth) min-entropy is lower bounded as follows:
$$ H_{min}^{epsilon}(X_1^n mid K Theta_1^n M) geq ngammaleft( frac{-log_2(d)}{n} right) – 1 – log_2left( frac{2}{epsilon^2} right), $$
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 Weak String Erasure for the definition.
Technical Description
Inputs: $n$
Output: $X_1^n$, $mathcal{I}$, $X_{mathcal{I}}$- Alice and Bob agree on a time $Delta t$.
- For $i in [n]$ do:
- Alice chooses uniformly at random $Theta_i in {0,1}$ and $X_i in {0,1}$.
- Alice prepares the state $H^{Theta_i}lvert X_i rangle$. She sends it over to Bob.
- Bob announces receiving a state.
- Bob chooses uniformly at random $hat{Theta}_i in {0,1}$.
- 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$.
- 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$.
- Alice and Bob wait for time $Delta t$.
- Alice sends $Theta_1^n$ to Bob.
- Bob computes $mathcal{I} := {i in [n] : Theta_i = hat{Theta}_i}$.
- 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}}$.
Experimental Implementations
No content has been added to this section, yet!
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 analysed in the presence of noise and losses [2]
References
- Konig, Robert, Stephanie Wehner, and Jürg Wullschleger. “Unconditional security from noisy quantum storage.” IEEE Transactions on Information Theory 58, no. 3 (2012): 1962-1984.
- Wehner, Stephanie, Marcos Curty, Christian Schaffner, and Hoi-Kwong Lo. “Implementation of two-party protocols in the noisy-storage model.” Physical Review A—Atomic, Molecular, and Optical Physics 81, no. 5 (2010): 052336.
- Wehner, Stephanie, Christian Schaffner, and Barbara M. Terhal. “Cryptography from noisy storage.” Physical Review Letters 100, no. 22 (2008): 220502.
- Schaffner, Christian. “Cryptography in the bounded-quantum-storage model.” arXiv preprint arXiv:0709.0289 (2007).
- Damgård, Ivan B., Serge Fehr, Louis Salvail, and Christian Schaffner. “Cryptography in the bounded-quantum-storage model.” SIAM Journal on Computing 37, no. 6 (2008): 1865-1890.
- 2025-05-16 at 14:41 by Mina Doosti
implements Weak String Erasure
Introduction
This protocol implements Weak String Erasure (WSE) in a prepare-and-measure setup. This is often used as a subroutine in other protocols.
Outline
Alice and Bob first agree on a duration $Delta_t$ that should correspond to an estimation of the time needed to make any known quantum memory decohere. 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 of their quantum state in their 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 on a different basis than Alice 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.
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] and [3]
- The transmission of the qubits is noiseless/lossless.
- The preparation devices (for quantum states) are assumed to be fully characterized and trusted. We assume the same for the measurement devices.
Requirements
Network Stage: Prepare and Measure.
Relevant Network Parameters: $epsilon _{T}, epsilon _{M}$ ( These distances are diamond norm distances between the states obtained from ideal quantum channels, measurement and real (noisy) quantum channels and measurement.)
The parties need a random number generator.
Notation
- $n$ be the total number of rounds.
- $A_1^n$ denotes the string $A_1, ldots, A_n$.
- $H$ denotes the Hadamard gate. $H^0 = I$ and $H^1 = H$.
- $X_1^n$ is the random string Alice sends to Bob via the WSE protocol.
- $Theta_i$ encodes Alice’s choice of basis in round $i$.
- $hat{X}_1^n$ is Bob’s measurement outcomes.
- $hat{Theta}_i$ encodes Bob’s choice of basis in round $i$.
- $M$ denotes dishonest Bob’s quantum memory, which can store a state of dimension at most $d$.
- $Delta t$ is the 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.
- $A_{mathcal{I}}$ denotes the substring of $A_1^n$ whose bits are in $mathcal{I}$.
Let us define the following function:
$$
gamma(x) :=
begin{cases}
x, & text{if } x > frac{1}{2} \\\\\\\\\
g^{-1}(x), & text{if } x leq frac{1}{2}
end{cases}
$$where
$$
g(x) := h(x) + x – 1, quad text{and} quad h(x) := -xlog(x) – (1-x)log(1-x)
$$Properties
- If (dishonest) Bob holds a quantum memory of dimension at most $d$, then his (smooth) min-entropy is lower bounded as follows:
$$ H_{min}^{epsilon}(X_1^n mid K Theta_1^n M) geq ngammaleft( frac{-log_2(d)}{n} right) – 1 – log_2left( frac{2}{epsilon^2} right), $$
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 Weak String Erasure for the definition.
Technical Description
Inputs: $n$
Output: $X_1^n$, $mathcal{I}$, $X_{mathcal{I}}$- Alice and Bob agree on a time $Delta t$.
- For $i in [n]$ do:
- Alice chooses uniformly at random $Theta_i in {0,1}$ and $X_i in {0,1}$.
- Alice prepares the state $H^{Theta_i}lvert X_i rangle$. She sends it over to Bob.
- Bob announces receiving a state.
- Bob chooses uniformly at random $hat{Theta}_i in {0,1}$.
- 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$.
- 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$.
- Alice and Bob wait for time $Delta t$.
- Alice sends $Theta_1^n$ to Bob.
- Bob computes $mathcal{I} := {i in [n] : Theta_i = hat{Theta}_i}$.
- 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}}$.
Experimental Implementations
No content has been added to this section, yet!
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 analysed in the presence of noise and losses [2]
References
- Konig, Robert, Stephanie Wehner, and Jürg Wullschleger. “Unconditional security from noisy quantum storage.” IEEE Transactions on Information Theory 58, no. 3 (2012): 1962-1984.
- Wehner, Stephanie, Marcos Curty, Christian Schaffner, and Hoi-Kwong Lo. “Implementation of two-party protocols in the noisy-storage model.” Physical Review A—Atomic, Molecular, and Optical Physics 81, no. 5 (2010): 052336.
- Wehner, Stephanie, Christian Schaffner, and Barbara M. Terhal. “Cryptography from noisy storage.” Physical Review Letters 100, no. 22 (2008): 220502.
- Schaffner, Christian. “Cryptography in the bounded-quantum-storage model.” arXiv preprint arXiv:0709.0289 (2007).
- 2025-05-16 at 14:41 by Mina Doosti
implements Weak String Erasure
Introduction
This protocol implements Weak String Erasure (WSE) in a prepare-and-measure setup. This is often used as a subroutine in other protocols.
Outline
Alice and Bob first agree on a duration $Delta_t$ that should correspond to an estimation of the time needed to make any known quantum memory decohere. 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 of their quantum state in their 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 on a different basis than Alice 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.
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] and [3]
- The transmission of the qubits is noiseless/lossless.
- The preparation devices (for quantum states) are assumed to be fully characterized and trusted. We assume the same for the measurement devices.
Requirements
Network Stage: Prepare and Measure.
Relevant Network Parameters: $epsilon _{T}, epsilon _{M}$ ( These distances are diamond norm distances between the states obtained from ideal quantum channels, measurement and real (noisy) quantum channels and measurement.)
The parties need a random number generator.
Notation
- $n$ be the total number of rounds.
- $A_1^n$ denotes the string $A_1, ldots, A_n$.
- $H$ denotes the Hadamard gate. $H^0 = I$ and $H^1 = H$.
- $X_1^n$ is the random string Alice sends to Bob via the WSE protocol.
- $Theta_i$ encodes Alice’s choice of basis in round $i$.
- $hat{X}_1^n$ is Bob’s measurement outcomes.
- $hat{Theta}_i$ encodes Bob’s choice of basis in round $i$.
- $M$ denotes dishonest Bob’s quantum memory, which can store a state of dimension at most $d$.
- $Delta t$ is the 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.
- $A_{mathcal{I}}$ denotes the substring of $A_1^n$ whose bits are in $mathcal{I}$.
Let us define the following function:
$$
gamma(x) :=
begin{cases}
x, & text{if } x > frac{1}{2} \\\\\\\\\
g^{-1}(x), & text{if } x leq frac{1}{2}
end{cases}
$$where
$$
g(x) := h(x) + x – 1, quad text{and} quad h(x) := -xlog(x) – (1-x)log(1-x)
$$Properties
- If (dishonest) Bob holds a quantum memory of dimension at most $d$, then his (smooth) min-entropy is lower bounded as follows:
$$ H_{min}^{epsilon}(X_1^n mid K Theta_1^n M) geq ngammaleft( frac{-log_2(d)}{n} right) – 1 – log_2left( frac{2}{epsilon^2} right), $$
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 Weak String Erasure for the definition.
Technical Description
Inputs: $n$
Output: $X_1^n$, $mathcal{I}$, $X_{mathcal{I}}$- Alice and Bob agree on a time $Delta t$.
- For $i in [n]$ do:
- Alice chooses uniformly at random $Theta_i in {0,1}$ and $X_i in {0,1}$.
- Alice prepares the state $H^{Theta_i}lvert X_i rangle$. She sends it over to Bob.
- Bob announces receiving a state.
- Bob chooses uniformly at random $hat{Theta}_i in {0,1}$.
- 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$.
- 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$.
- Alice and Bob wait for time $Delta t$.
- Alice sends $Theta_1^n$ to Bob.
- Bob computes $mathcal{I} := {i in [n] : Theta_i = hat{Theta}_i}$.
- 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}}$.
Experimental Implementations
No content has been added to this section, yet!
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 analysed in the presence of noise and losses [2]
References
- Konig, Robert, Stephanie Wehner, and Jürg Wullschleger. “Unconditional security from noisy quantum storage.” IEEE Transactions on Information Theory 58, no. 3 (2012): 1962-1984.
- Wehner, Stephanie, Marcos Curty, Christian Schaffner, and Hoi-Kwong Lo. “Implementation of two-party protocols in the noisy-storage model.” Physical Review A—Atomic, Molecular, and Optical Physics 81, no. 5 (2010): 052336.
- Wehner, Stephanie, Christian Schaffner, and Barbara M. Terhal. “Cryptography from noisy storage.” Physical Review Letters 100, no. 22 (2008): 220502.
- Schaffner, Christian. “Cryptography in the bounded-quantum-storage model.” arXiv preprint arXiv:0709.0289 (2007).