dorsal/arxiv
View SchemaSmall Pseudo-Random Families of Matrices: Derandomizing Approximate Quantum Encryption
| Authors | Andris Ambainis, Adam Smith |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0404075 |
| URL | https://arxiv.org/abs/quant-ph/0404075 |
Abstract
A quantum encryption scheme (also called private quantum channel, or state randomization protocol) is a one-time pad for quantum messages. If two parties share a classical random string, one of them can transmit a quantum state to the other so that an eavesdropper gets little or no information about the state being transmitted. Perfect encryption schemes leak no information at all about the message. Approximate encryption schemes leak a non-zero (though small) amount of information but require a shorter shared random key. Approximate schemes with short keys have been shown to have a number of applications in quantum cryptography and information theory. This paper provides the first deterministic, polynomial-time constructions of quantum approximate encryption schemes with short keys. Previous constructions (quant-ph/0307104) are probabilistic--that is, they show that if the operators used for encryption are chosen at random, then with high probability the resulting protocol will be a secure encryption scheme. Moreover, the resulting protocol descriptions are exponentially long. Our protocols use keys of the same length as (or better length than) the probabilistic constructions; to encrypt $n$ qubits approximately, one needs $n+o(n)$ bits of shared key. An additional contribution of this paper is a connection between classical combinatorial derandomization and constructions of pseudo-random matrix families in a continuous space.
{
"annotation_id": "6fcd2539-b9ab-441e-a73e-0238d5528b50",
"date_created": "2026-03-02T18:02:06.807000Z",
"date_modified": "2026-03-02T18:02:06.807000Z",
"file_hash": "88a8af6c86b7e35c36a4204183230e67133cad21ba8bcddce47bb57b001be467",
"private": false,
"record": {
"abstract": "A quantum encryption scheme (also called private quantum channel, or state\nrandomization protocol) is a one-time pad for quantum messages. If two parties\nshare a classical random string, one of them can transmit a quantum state to\nthe other so that an eavesdropper gets little or no information about the state\nbeing transmitted. Perfect encryption schemes leak no information at all about\nthe message. Approximate encryption schemes leak a non-zero (though small)\namount of information but require a shorter shared random key. Approximate\nschemes with short keys have been shown to have a number of applications in\nquantum cryptography and information theory.\n This paper provides the first deterministic, polynomial-time constructions of\nquantum approximate encryption schemes with short keys. Previous constructions\n(quant-ph/0307104) are probabilistic--that is, they show that if the operators\nused for encryption are chosen at random, then with high probability the\nresulting protocol will be a secure encryption scheme. Moreover, the resulting\nprotocol descriptions are exponentially long. Our protocols use keys of the\nsame length as (or better length than) the probabilistic constructions; to\nencrypt $n$ qubits approximately, one needs $n+o(n)$ bits of shared key.\n An additional contribution of this paper is a connection between classical\ncombinatorial derandomization and constructions of pseudo-random matrix\nfamilies in a continuous space.",
"arxiv_id": "quant-ph/0404075",
"authors": [
"Andris Ambainis",
"Adam Smith"
],
"categories": [
"quant-ph",
"cs.CR"
],
"title": "Small Pseudo-Random Families of Matrices: Derandomizing Approximate Quantum Encryption",
"url": "https://arxiv.org/abs/quant-ph/0404075"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "38fa95e8-a0e0-4bf3-9c19-302f6a2a5dec",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}