Continuously Non-malleable Codes with Split-State Refresh

Antonio Faonio, Jesper Buus Nielsen, Mark Simkin, Daniele Venturi

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


Non-malleable codes for the split-state model allow to encode a message into two parts, such that arbitrary independent tampering on each part, and subsequent decoding of the corresponding modified codeword, yields either the same as the original message, or a completely unrelated value. Continuously non-malleable codes further allow to tolerate an unbounded (polynomial) number of tampering attempts, until a decoding error happens. The drawback is that, after an error happens, the system must self-destruct and stop working, otherwise generic attacks become possible. In this paper we propose a solution to this limitation, by leveraging a split-state refreshing procedure. Namely, whenever a decoding error happens, the two parts of an encoding can be locally refreshed (i.e., without any interaction), which allows to avoid the self-destruct mechanism. An additional feature of our security model is that it captures directly security against continual leakage attacks. We give an abstract framework for building such codes in the common reference string model, and provide a concrete instantiation based on the external Diffie-Hellman assumption. Finally, we explore applications in which our notion turns out to be essential. The first application is a signature scheme tolerating an arbitrary polynomial number of split-state tampering attempts, without requiring a self-destruct capability, and in a model where refreshing of the memory happens only after an invalid output is produced. This circumvents an impossibility result from a recent work by Fuijisaki and Xagawa (Asiacrypt 2016). The second application is a compiler for tamper-resilient RAM programs. In comparison to other tamper-resilient compilers, ours has several advantages, among which the fact that, for the first time, it does not rely on the self-destruct feature.

Original languageEnglish
Title of host publicationApplied Cryptography and Network Security - 16th International Conference, ACNS 2018, Proceedings
EditorsBart Preneel, Frederik Vercauteren
Number of pages19
Place of publicationCham
PublisherSpringer VS
Publication date2018
ISBN (Print)978-3-319-93387-0
Publication statusPublished - 2018
EventThe 16th International Conference on Applied Cryptography and Network Security - Leuven, Belgium
Duration: 2 Jul 20184 Jul 2018
Conference number: 16


ConferenceThe 16th International Conference on Applied Cryptography and Network Security
Internet address
SeriesLecture Notes in Computer Science (LNCS)


  • Non-malleable codes
  • Tamper-resilient cryptography


Dive into the research topics of 'Continuously Non-malleable Codes with Split-State Refresh'. Together they form a unique fingerprint.

Cite this