Paper 2017/930
Fourstate Nonmalleable Codes with Explicit Constant Rate
Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar
Abstract
Nonmalleable 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$splitstate 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 Rate1 nonmalleable code for the case where $t = O(n)$ with $n$ being the codeword length and, in (ITCS 2014), show an upper bound of $11/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 nonmalleable code in the $t$splitstate 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published by the IACR in TCC 2017
 Keywords
 information theoretic cryptographynonmalleability
 Contact author(s)

bhavana @ iisc ac in
oslbhavana @ gmail com
sruthi sekar1 @ gmail com  History
 20170925: received
 Short URL
 https://ia.cr/2017/930
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/930, author = {Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Sruthi Sekar}, title = {Fourstate Nonmalleable Codes with Explicit Constant Rate}, howpublished = {Cryptology ePrint Archive, Paper 2017/930}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/930}}, url = {https://eprint.iacr.org/2017/930} }