dorsal/arxiv
View SchemaAuthentication of Quantum Messages
| Authors | Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, Alain Tapp |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0205128 |
| URL | https://arxiv.org/abs/quant-ph/0205128 |
| DOI | 10.1109/SFCS.2002.1181969 |
| Journal | Proc. 43rd Annual IEEE Symposium on the Foundations of Computer Science (FOCS '02), pp. 449-458. IEEE Press, 2002. |
Abstract
Authentication is a well-studied area of classical cryptography: a sender S and a receiver R sharing a classical private key want to exchange a classical message with the guarantee that the message has not been modified by any third party with control of the communication line. In this paper we define and investigate the authentication of messages composed of quantum states. Assuming S and R have access to an insecure quantum channel and share a private, classical random key, we provide a non-interactive scheme that enables S both to encrypt and to authenticate (with unconditional security) an m qubit message by encoding it into m+s qubits, where the failure probability decreases exponentially in the security parameter s. The classical private key is 2m+O(s) bits. To achieve this, we give a highly efficient protocol for testing the purity of shared EPR pairs. We also show that any scheme to authenticate quantum messages must also encrypt them. (In contrast, one can authenticate a classical message while leaving it publicly readable.) This has two important consequences: On one hand, it allows us to give a lower bound of 2m key bits for authenticating m qubits, which makes our protocol asymptotically optimal. On the other hand, we use it to show that digitally signing quantum states is impossible, even with only computational security.
{
"annotation_id": "76caf58f-8f36-44ef-8bd3-80ce4a6a0997",
"date_created": "2026-03-02T18:01:52.614000Z",
"date_modified": "2026-03-02T18:01:52.614000Z",
"file_hash": "7ca3d7ca264a5b162486d9ef715dc79e58346e281e9d61cd920d5d082f5d8aae",
"private": false,
"record": {
"abstract": "Authentication is a well-studied area of classical cryptography: a sender S\nand a receiver R sharing a classical private key want to exchange a classical\nmessage with the guarantee that the message has not been modified by any third\nparty with control of the communication line. In this paper we define and\ninvestigate the authentication of messages composed of quantum states. Assuming\nS and R have access to an insecure quantum channel and share a private,\nclassical random key, we provide a non-interactive scheme that enables S both\nto encrypt and to authenticate (with unconditional security) an m qubit message\nby encoding it into m+s qubits, where the failure probability decreases\nexponentially in the security parameter s. The classical private key is 2m+O(s)\nbits. To achieve this, we give a highly efficient protocol for testing the\npurity of shared EPR pairs. We also show that any scheme to authenticate\nquantum messages must also encrypt them. (In contrast, one can authenticate a\nclassical message while leaving it publicly readable.) This has two important\nconsequences: On one hand, it allows us to give a lower bound of 2m key bits\nfor authenticating m qubits, which makes our protocol asymptotically optimal.\nOn the other hand, we use it to show that digitally signing quantum states is\nimpossible, even with only computational security.",
"arxiv_id": "quant-ph/0205128",
"authors": [
"Howard Barnum",
"Claude Crepeau",
"Daniel Gottesman",
"Adam Smith",
"Alain Tapp"
],
"categories": [
"quant-ph",
"cs.CR"
],
"doi": "10.1109/SFCS.2002.1181969",
"journal_ref": "Proc. 43rd Annual IEEE Symposium on the Foundations of Computer\n Science (FOCS \u002702), pp. 449-458. IEEE Press, 2002.",
"title": "Authentication of Quantum Messages",
"url": "https://arxiv.org/abs/quant-ph/0205128"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b00e85a3-c1db-40ca-a24d-42dd45d6ad46",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}