Keyless secrecy against bounded adversaries
Abstract
We introduce a keyless coding/cryptographic primitive that asks for two guarantees at once: the receiver is never fooled into accepting a message other than the one sent, and the adversary learns nothing about the message unless the receiver aborts. Neither the sender nor the receiver holds a secret key, and no computational hardness is assumed. The only restriction is on the adversary's online computation: the receiver aborts if nothing arrives by a fixed deadline, so the adversary must forward something before it, and her map in that window is computed by a circuit of size (or depth) at most p; before and after, she is unbounded. For every polynomial p we construct such an efficient quantum scheme, encoding k-bit messages into n = O(k) qubits with circuits of size poly(n,p). No classical scheme achieves this type of everlasting security, at any choice of parameters. Our techniques also resolve open questions about universal tamper detection against families restricted in cardinality rather than in circuit size. We settle a question of Broadbent, Kapshikar and Rochette on relaxed tamper detection. As a corollary, we obtain the first efficient non-malleable code secure against global quantum tampering, with no split-state restriction, whereas the current constructions in the literature require the codeword to be split into non-communicating shares.
Related
- Efficient multi-basis quantum position verification secure against generalized adversaries
- Certified Randomness Generation against Quantum Adversaries via Energy Constraints
- From Symmetry to Secrecy: Covariant Classical--Quantum Wiretap Channels
- Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know
- On vacua and bounded masses in the general 2HDM
BibTeX
@misc{broadbent2026keyless,
title = {{Keyless secrecy against bounded adversaries}},
author = {Anne Broadbent and Upendra Kapshikar and Denis Rochette},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.12251},
eprint = {2609.12251},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12251},
}
RIS
TY - UNPB
TI - Keyless secrecy against bounded adversaries
AU - Anne Broadbent
AU - Upendra Kapshikar
AU - Denis Rochette
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2609.12251
UR - https://arxiv.org/abs/2609.12251
AB - We introduce a keyless coding/cryptographic primitive that asks for two guarantees at once: the receiver is never fooled into accepting a message other than the one sent, and the adversary learns nothing about the message unless the receiver aborts. Neither the sender nor the receiver holds a secret key, and no computational hardness is assumed. The only restriction is on the adversary's online computation: the receiver aborts if nothing arrives by a fixed deadline, so the adversary must forward something before it, and her map in that window is computed by a circuit of size (or depth) at most p; before and after, she is unbounded. For every polynomial p we construct such an efficient quantum scheme, encoding k-bit messages into n = O(k) qubits with circuits of size poly(n,p). No classical scheme achieves this type of everlasting security, at any choice of parameters. Our techniques also resolve open questions about universal tamper detection against families restricted in cardinality rather than in circuit size. We settle a question of Broadbent, Kapshikar and Rochette on relaxed tamper detection. As a corollary, we obtain the first efficient non-malleable code secure against global quantum tampering, with no split-state restriction, whereas the current constructions in the literature require the codeword to be split into non-communicating shares.
ER -