Revision History for: Weak String Erasure
- 2025-06-24 at 21:29 by JuliaM
Functionality Description
Weak String Erasure (WSE)[1] 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.
This primitive is secure against quantum adversaries and can be realised under the noisy-storage model, where adversaries are assumed to have bounded or imperfect quantum memory during the protocol execution.
Protocols
The protocols that implement this functionality are:
Classical Analogues
There is no direct classical analogue of weak string erasure, under unconditional or minimal assumptions. WSE is a fundamentally quantum promitive that exploits quantum uncertainty and measurement disturbance, features absent in classical information theory.
However, it can be seen as a quantum generalisation of oblivious transfer correlations and shares conceptual similarities with primitives like private information retrieval and random oblivious transfer, though those require additional assumptions or interaction to achieve security classically.
Real-world Use Cases
Weak String Erasure is a primitive and a building block in other protocols such as oblivious transfer.
It doesn’t have a direct real-world use caseProperties
Let $n$ be the total length of the string. A WSE functionality $\\\mathcal{F}_{\\\mathrm{WSE}}$ proceeds as follows:
- Alice receives $X^n \\\in \\\{0,1\\\}^n$ uniformly at random.
- Bob receives $(I, X_I)$, where $I \\\subseteq [n]$ is chosen uniformly at random, and $X_I$ is the restriction of $X^n$ to the indices in $I$.
The security properties are:
Correctness: If both parties are honest, outputs are distributed as above.
Sender security: A malicious Bob learns nothing about $X_{[n] \\\setminus I}$.
Receiver security: A malicious Alice learns nothing about $I$.
Some other properties include:
One-way correlation: Only Alice knows the full string $X^n$ while Bob learns part of it.
Uncertainty-based security: Security arises from quantum measurement limits and the inability to store all quantum information.
Receiver obliviousness: Alice learns nothing about Bob’s index set
Post-processing ready: Can be extended via privacy amplification to build secure keys or oblivious transfer.Further Information
- WSE is complete for two-party cryptography in the noisy-storage model.
- It provides a quantum analogue to Oblivious Transfer extensions, where multiple higher-level functionalities can be derived from WSE with only classical post-processing and one round of quantum communication.
- Protocol simplicity: Often involves prepare-and-measure protocols with BB84 encoding and delayed basis revelation.
- Experimental implementations: Realisations of WSE-based OT protocols have been tested in experimental quantum communication systems.
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.
- 2025-05-16 at 14:13 by Mina Doosti
Functionality Description
Weak String Erasure (WSE)[1] 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.
This primitive is secure against quantum adversaries and can be realised under the noisy-storage model, where adversaries are assumed to have bounded or imperfect quantum memory during the protocol execution.
Protocols
No protocols implement this functionality yet.
Classical Analogues
There is no direct classical analogue of weak string erasure, under unconditional or minimal assumptions. WSE is a fundamentally quantum promitive that exploits quantum uncertainty and measurement disturbance, features absent in classical information theory.
However, it can be seen as a quantum generalisation of oblivious transfer correlations and shares conceptual similarities with primitives like private information retrieval and random oblivious transfer, though those require additional assumptions or interaction to achieve security classically.
Real-world Use Cases
Weak String Erasure is a primitive and a building block in other protocols such as oblivious transfer.
It doesn’t have a direct real-world use caseProperties
Let $n$ be the total length of the string. A WSE functionality $mathcal{F}_{mathrm{WSE}}$ proceeds as follows:
- Alice receives $X^n in {0,1}^n$ uniformly at random.
- Bob receives $(I, X_I)$, where $I subseteq [n]$ is chosen uniformly at random, and $X_I$ is the restriction of $X^n$ to the indices in $I$.
The security properties are:
Correctness: If both parties are honest, outputs are distributed as above.
Sender security: A malicious Bob learns nothing about $X_{[n] setminus I}$.
Receiver security: A malicious Alice learns nothing about $I$.
Some other properties include:
One-way correlation: Only Alice knows the full string $X^n$ while Bob learns part of it.
Uncertainty-based security: Security arises from quantum measurement limits and the inability to store all quantum information.
Receiver obliviousness: Alice learns nothing about Bob’s index set
Post-processing ready: Can be extended via privacy amplification to build secure keys or oblivious transfer.Further Information
- WSE is complete for two-party cryptography in the noisy-storage model.
- It provides a quantum analogue to Oblivious Transfer extensions, where multiple higher-level functionalities can be derived from WSE with only classical post-processing and one round of quantum communication.
- Protocol simplicity: Often involves prepare-and-measure protocols with BB84 encoding and delayed basis revelation.
- Experimental implementations: Realisations of WSE-based OT protocols have been tested in experimental quantum communication systems.
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.