Rate 1/5 Non-Malleable Codes against Entangled Split-State Tampering

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 $\xi>0$ and all sufficiently large first-share lengths $n$, the codes have rate at least $1/5-\xi$, perfect correctness, and error $2^{-n^{\Omega(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.

Quantum Physics (quant-ph); Cryptography and Security (cs.CR)

arXiv:2609.39589 [quant-ph]

(or arXiv:2609.39589v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.39589 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.