@inproceedings{gupta2019explicit,
author = {Gupta, Divya and Maji, Hemanta and Wang, Mingyuan},
title = {Explicit Rate-1 Non-malleable Codes for Local Tampering},
booktitle = {CRYPTO},
year = {2019},
month = {August},
abstract = {This paper constructs high-rate non-malleable codes in the information-theoretic plain model against tampering functions with bounded locality. We consider δ-local tampering functions; namely, each output bit of the tampering function is a function of (at most) δ input bits. This work presents the first explicit and efficient rate-1 non-malleable code for δ-local tampering functions, where δ=ξ lgn and ξ<1
ξ<1

is any positive constant. As a corollary, we construct the first explicit rate-1 non-malleable code against NC0

0

tampering functions.
Before our work, no explicit construction for a constant-rate non-malleable code was known even for the simplest 1-local tampering functions. Ball et al. (EUROCRYPT–2016), and Chattopadhyay and Li (STOC–2017) provided the first explicit non-malleable codes against δ
δ

-local tampering functions. However, these constructions are rate-0 even when the tampering functions have 1-locality. In the CRS model, Faust et al. (EUROCRYPT–2014) constructed efficient rate-1 non-malleable codes for δ=O(logn)

δ=O(log⁡n)

local tampering functions.
Our main result is a general compiler that bootstraps a rate-0 non-malleable code against leaky input and output local tampering functions to construct a rate-1 non-malleable code against ξlgn
ξlg⁡n

-local tampering functions, for any positive constant ξ<1

ξ<1

. Our explicit construction instantiates this compiler using an appropriate encoding by Ball et al. (EUROCRYPT–2016).},
url = {http://approjects.co.za/?big=en-us/research/publication/explicit-rate-1-non-malleable-codes-for-local-tampering/},
}