## CryptoDB

### Paper: Four-State Non-malleable Codes with Explicit Constant Rate

Authors: Bhavana Kanukurthi Sai Lakshmi Bhavana Obbattu Sruthi Sekar DOI: 10.1007/s00145-019-09339-7 Search ePrint Search Google Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs (ITCS 2010), provide a powerful guarantee in scenarios where the classical notion of error-correcting codes cannot provide any guarantee: a decoded message is either the same or completely independent of the underlying message, regardless of the number of errors introduced into the codeword. Informally, NMCs are defined with respect to a family of tampering functions $\mathcal {F}$ F and guarantee that any tampered codeword decodes either to the same message or to an independent message, so long as it is tampered using a function $f \in \mathcal {F}$ f ∈ F . One of the well-studied tampering families for NMCs is the t -split-state family, where the adversary tampers each of the t “states” of a codeword, arbitrarily but independently. Cheraghchi and Guruswami (TCC 2014) obtain a rate-1 non-malleable code for the case where $t = \mathcal {O}(n)$ t = O ( n ) with n being the codeword length and, in (ITCS 2014), show an upper bound of $1-1/t$ 1 - 1 / t on the best achievable rate for any t -split state NMC. For $t=10$ t = 10 , Chattopadhyay and Zuckerman (FOCS 2014) achieve a constant-rate construction where the constant is unknown. In summary, there is no known construction of an NMC with an explicit constant rate for any $t= o(n)$ t = o ( n ) , let alone one that comes close to matching Cheraghchi and Guruswami’s lowerbound! In this work, we construct an efficient non-malleable code in the t -split-state model, for $t=4$ t = 4 , that achieves a constant rate of $\frac{1}{3+\zeta }$ 1 3 + ζ , for any constant $\zeta > 0$ ζ > 0 , and error $2^{-\varOmega (\ell / log^{c+1} \ell )}$ 2 - Ω ( ℓ / l o g c + 1 ℓ ) , where $\ell$ ℓ is the length of the message and $c > 0$ c > 0 is a constant.
##### BibTeX
@article{jofc-2019-30114,
title={Four-State Non-malleable Codes with Explicit Constant Rate},
journal={Journal of Cryptology},
publisher={Springer},
doi={10.1007/s00145-019-09339-7},
author={Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Sruthi Sekar},
year=2019
}