2026-09-20T12:50:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25349 2026-09-05T19:14:05Z ddc:004 open_access

Improved Rate for Non-Malleable Codes and Time-Lock Puzzles Freitag, Cody Komargodski, Ilan Kondapaneni, Manu Silbak, Jad Non-malleable codes Time-lock puzzles 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Cody Freitag and Ilan Komargodski and Manu Kondapaneni and Jad Silbak 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.62 urn:nbn:de:0030-drops-253490 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.62 eng https://creativecommons.org/licenses/by/4.0/legalcode