### Continuously Non-Malleable Codes against Bounded-Depth Tampering

##### Abstract

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)
Category
Foundations
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
Keywords
non-malleability leakage resilience decision trees bounded-depth circuits
Contact author(s)
brian @ di uniroma1 it
venturi @ di uniroma1 it
History
2022-09-19: approved
See all versions
Short URL
https://ia.cr/2022/1231

CC BY

BibTeX

@misc{cryptoeprint:2022/1231,
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{https://eprint.iacr.org/2022/1231}},
url = {https://eprint.iacr.org/2022/1231}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.