Non-Malleable Coding under Cost Constraints

We consider a communication problem where sender, say Alice, sends a message to receiver, say Bob, in the presence of an active adversary, James, who tampers Alice's transmission using a function from a known class of tampering functions. The goal is two-fold: First, the decoder should always decode Alice's message correctly in the absence of tampering. Second, when tampering occurs, the decoder should attempt to detect errors and, when that fails, limit the adversary's control over the decoding error outcome. In particular, the decoded message should be statistically independent of Alice's original message, making the coding scheme non-malleable (with respect to tampering). This setup is motivated by scenarios like tampered-proof sealed-bid auctions, where an adversary might attempt to alter the decoded bid to manipulate the outcome. In this work, we focus on binary non-malleable coding with input constraints, which limit the set of possible transmit vectors. We fully characterize the maximum throughput, or non-malleable capacity, for any given tampering family of bounded size (up to doubly-exponential in block length), extending the classic result for unconstrained inputs by Cheragchi and Guruswami (Trans. IT, 2016)