(2026-04) Improved Rate for Non-Malleable Codes and Time-Lock Puzzles
2026-04-15
Non-malleable codes allow a sender to transmit a message to a receiver, while providing a ``best-possible'' integrity guarantee to ensure that no attacker—who cannot already decode the message—can meaningfully tamper the message in transit. If tampered, the received message should either be invalid or unrelated to the original message. Non-malleable time-lock puzzles (TLPs) are a special case of non-malleable codes for bounded polynomial-depth tampering with very efficient encoding.
In this work, we give generic techniques for constructing non-malleable codes and non-malleable TLPs with improved rate, which captures the ratio of a message's length to its encoding length.
A key contribution of our work is identifying a security notion for non-malleability, which we term ``CCA-hiding'', sufficient for our compilers. CCA-hiding is a relaxation of CCA-security for encryption or commitments to the fine-grained setting of codes, and requires that the encoded message remains hidden, even given a decoding oracle for any other codeword. Intriguingly, CCA-hiding does not imply non-malleability in the fine-grained setting, as is the case for encryption and commitments.
Using our new techniques, we give the following constructions: -- Rate-1 CCA-hiding TLPs in the plain model. -- Rate-1 non-malleable codes for bounded polynomial-depth tampering in the auxiliary-input random oracle model (AI-ROM). -- Rate-(1/2) non-malleable TLPs in the AI-ROM.