arXiv:2609.39589
Rate 1/5 Non-Malleable Codes against Entangled Split-State Tampering
Naresh Goud Boddu
Abstract
We construct efficient information-theoretic non-malleable codes for classical messages that are secure against two noncommunicating local quantum tampering operations with arbitrary pre-shared entanglement. For every sufficiently small fixed $ξ>0$ and all sufficiently large first-share lengths $n$, the codes have rate at least $1/5-ξ$, perfect correctness, and error $2^{-n^{Ω(1)}}$. Security holds for every message, with a single message-independent simulator for each attack. This resolves the constant-rate question for worst-case classical messages in the entangled two-split-state model. Our construction builds on the permutation-based two-split construction of Batra, Boddu, and Jain, which achieves rate approaching $1/5$ for uniformly random messages. We retain their architecture but replace the uniform message input to the permutation with a prescribed message concatenated with fresh uniform padding. Our main contribution is a worst-case security reduction for this modification.
AI Summary
The paper addresses whether efficient, information-theoretic two-split-state non-malleable codes can achieve constant rate for every classical message against noncommunicating quantum tampering operations with arbitrary pre-shared entanglement. Previous constructions provided worst-case security at vanishing rate or rate approaching $1/5$ only for uniformly random messages. It modifies the BBJ permutation-based construction by padding a prescribed message with fresh randomness before applying an affine permutation keyed by a non-malleable randomness encoder. For every sufficiently small fixed $\xi>0$, the resulting code has rate at least $1/5-\xi$, perfect correctness, polynomial-time encoding and decoding, and error $2^{-n^{\Omega(1)}}$, where $n$ is the first-share length. Each attack admits one message-independent simulator valid for all messages. The rate counts unequal share lengths; padding to equal-length shares yields rate approaching $1/8$. The security reduction avoids the exponential error amplification associated with conditioning uniform-message security on a fixed message. It factors the quantum attack into a coarse operation and an exact continuation preserving entangled correlations, invokes BBJ before message selection, and controls selection using two exact trace normalizations and a bounded-deficit comparison for completely positive maps. Affine-permutation second moments bound noncommuting fluctuations. With inner error $\eta$, padding length $r$, and second-source length $d$, the reduction gives error $O(\sqrt\eta+2^{-(r-d)/5})$ for $r>d$. Security concerns decoded-message distributions, not joint simulation of retained adversarial quantum registers. Messages and codewords remain classical. The error exponent is not claimed optimal, and the construction does not improve known exponential-error guarantees against classical tampering.
AI systems were subsequently used for further proof discussions and for drafting and revising early versions of the manuscript.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.