Skip to content
Preprint

Keyless secrecy against bounded adversaries

Sep 2026 · 0 citations · 33 references
Physics

TL;DR

The first efficient non-malleable code secure against global quantum tampering, with no split-state restriction, is obtained, whereas the current constructions in the literature require the codeword to be split into non-communicating shares.

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 $\mathrm{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.

View source

Similar papers

Preprint Sep 2026

Breaking the Bounded Entanglement Barrier for Quantum Position Verification

Position verification, introduced by Chandran et al. (SIAM J. Computing 2014), allows verifiers to test a prover's claimed position by an interactive protocol. Classical position verification is impossible. Even for Quantum Position Verification (QPV), there always exists an LOCC (Local Operations and Classical Communi...

Amit Behera, Vipul Goyal · 0 citations
Preprint Oct 2026

On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages

Multiparty Private Simultaneous Messages (PSM), also known as Decomposable Randomized Encoding (DRE) or information-theoretic garbling, is a model for non-interactive secure computation. Each party encodes its input using shared randomness and sends a message to an evaluator who does not know that randomness. The evalu...

Marshall Ball, Peter Crawford-Kahrl, V. Podolskii et al. · 0 citations
Sep 2026

Quantum Leakage Resilience of Shamir Secret Sharing

The study of quantum leakage resilience of unmodified Shamir secret sharing over prime fields shows that the maximum number of devices that may share arbitrary entanglement with one another and with the adversary while preserving security is linear in $n$ up to constant factors, although the optimal support fraction re...

Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki et al. · 1 citation · ⚡1
Preprint Sep 2026

Quantum Secret Sharing and Error Correction vs No-Cloning

This work proposes a variant of quantum secret sharing where two or more identical copies of the input state are provided, but the output is only required to recover one copy, and gives positive results showing that multiple copies allow for going slightly beyond the single-copy obstruction.

Steve Chien, Ishani Mukherjee, Mark Zhandry · 0 citations
Preprint Sep 2026

Quantum key distribution using generalized contextuality against post-quantum eavesdroppers

Bell nonlocality allows secret key to be certified without trusting the internal operation of the devices, and even against eavesdroppers constrained only by the no-signaling principle. We ask whether generalized contextuality, a notion of nonclassicality available in prepare-and-measure experiments on a single system,...

Daniel Centeno, Roberto D. Baldijão, Maria Ciudad Alan'on et al. · 0 citations
Preprint Oct 2026

Secret Sharing from Non-Extractable Randomness

Bosley and Dodis (TCC 2007) proved that a class of imperfect randomness sources that suffices for information-theoretic encryption of messages longer than the logarithm of the key length must admit deterministic extraction of nearly uniform bits, and asked whether the same is true of two-out-of-two secret sharing. Agga...

Divesh Aggarwal · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.