Paper 2022/1231

Continuously Non-Malleable Codes against Bounded-Depth Tampering

Gianluca Brian, Sapienza University of Rome
Sebastian Faust, TU Darmstadt
Elena Micheli, TU Darmstadt
Daniele Venturi, Sapienza University of Rome

Non-malleable codes (Dziembowski, Pietrzak and Wichs, ICS 2010 & JACM 2018) allow protecting arbitrary cryptographic primitives against related-key attacks (RKAs). Even when using codes that are guaranteed to be non-malleable against a single tampering attempt, one obtains RKA security against poly-many tampering attacks at the price of assuming perfect memory erasures. In contrast, continuously non-malleable codes (Faust, Mukherjee, Nielsen and Venturi, TCC 2014) do not suffer from this limitation, as the non-malleability guarantee holds against poly-many tampering attempts. Unfortunately, there are only a handful of constructions of continuously non-malleable codes, while standard non-malleable codes are known for a large variety of tampering families including, e.g., NC0 and decision-tree tampering, AC0, and recently even bounded polynomial-depth tampering. We change this state of affairs by providing the first constructions of continuously non-malleable codes in the following natural settings: - Against decision-tree tampering, where, in each tampering attempt, every bit of the tampered codeword can be set arbitrarily after adaptively reading up to $d$ locations within the input codeword. Our scheme is in the plain model, can be instantiated assuming the existence of one-way functions, and tolerates tampering by decision trees of depth $d = O(n^{1/8})$, where $n$ is the length of the codeword. Notably, this class includes NC0. - Against bounded polynomial-depth tampering, where in each tampering attempt the adversary can select any tampering function that can be computed by a circuit of bounded polynomial depth (and unbounded polynomial size). Our scheme is in the common reference string model, and can be instantiated assuming the existence of time-lock puzzles and simulation-extractable (succinct) non-interactive zero-knowledge proofs.

Note: Full version

Available format(s)
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
non-malleability leakage resilience decision trees bounded-depth circuits
Contact author(s)
brian @ di uniroma1 it
sebastian faust @ tu-darmstadt de
elena micheli @ tu-darmstadt de
venturi @ di uniroma1 it
2022-09-19: approved
2022-09-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gianluca Brian and Sebastian Faust and Elena Micheli and Daniele Venturi},
      title = {Continuously Non-Malleable Codes against Bounded-Depth Tampering},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1231},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.