Welcome to the resource topic for 2017/930
Title:
Four-state Non-malleable Codes with Explicit Constant Rate
Authors: Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Sruthi Sekar
Abstract:Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs (ITCS 2010), generalize the classical notion of error correcting codes by providing a powerful guarantee even in scenarios where 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 F and guarantee that any tampered codeword either decodes to the same message or to an independent message, so long as it is tampered using a function f \in F. Nearly all known constructions of NMCs are for the t-split-state family, where the adversary tampers each of the t blocks (also known as states), of a codeword, arbitrarily but independently. Cheraghchi and Guruswami (TCC 2014) obtain a Rate-1 non-malleable code for the case where t = O(n) with n being the codeword length and, in (ITCS 2014), show an upper bound of 1-1/t on the best achievable rate for any $t-$split state NMC. For 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), 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, that achieves a constant rate of \frac{1}{3+\zeta}, for any constant \zeta > 0, and error 2^{-\Omega(\ell / log^{c+1} \ell)}, where \ell is the length of the message and c > 0 is a constant.
ePrint: https://eprint.iacr.org/2017/930
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .