dorsal/arxiv
View SchemaCryptography In the Bounded Quantum-Storage Model
| Authors | Ivan Damgaard, Serge Fehr, Louis Salvail, Christian Schaffner |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0508222 |
| URL | https://arxiv.org/abs/quant-ph/0508222 |
| Journal | Proceedings of the 46th IEEE Symposium on Foundations of Computer Science - FOCS 2005, pages 449-458 |
Abstract
We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least n/2 in order to break the protocol, where n is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.
{
"annotation_id": "857fb8d5-867f-4b8c-bab6-632b8af7caa2",
"date_created": "2026-03-02T18:02:20.476000Z",
"date_modified": "2026-03-02T18:02:20.476000Z",
"file_hash": "2984ba1fa457c6ff9396ae18b2cce39e9e5f60486a1b7f073fb0519bb9d7e074",
"private": false,
"record": {
"abstract": "We initiate the study of two-party cryptographic primitives with\nunconditional security, assuming that the adversary\u0027s quantum memory is of\nbounded size. We show that oblivious transfer and bit commitment can be\nimplemented in this model using protocols where honest parties need no quantum\nmemory, whereas an adversarial player needs quantum memory of size at least n/2\nin order to break the protocol, where n is the number of qubits transmitted.\nThis is in sharp contrast to the classical bounded-memory model, where we can\nonly tolerate adversaries with memory of size quadratic in honest players\u0027\nmemory size. Our protocols are efficient, non-interactive and can be\nimplemented using today\u0027s technology. On the technical side, a new entropic\nuncertainty relation involving min-entropy is established.",
"arxiv_id": "quant-ph/0508222",
"authors": [
"Ivan Damgaard",
"Serge Fehr",
"Louis Salvail",
"Christian Schaffner"
],
"categories": [
"quant-ph",
"cs.CR"
],
"journal_ref": "Proceedings of the 46th IEEE Symposium on Foundations of Computer\n Science - FOCS 2005, pages 449-458",
"title": "Cryptography In the Bounded Quantum-Storage Model",
"url": "https://arxiv.org/abs/quant-ph/0508222"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "f02b53ce-b343-4669-8295-b3578d54c337",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}