Four-state Non-malleable Codes with Explicit Constant Rate

Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and 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.

Available format(s)
Category
Foundations
Publication info
Keywords
information theoretic cryptographynon-malleability
Contact author(s)
bhavana @ iisc ac in
oslbhavana @ gmail com
sruthi sekar1 @ gmail com
History
Short URL
https://ia.cr/2017/930

CC BY

BibTeX

@misc{cryptoeprint:2017/930,
author = {Bhavana Kanukurthi and Sai Lakshmi Bhavana Obbattu and Sruthi Sekar},
title = {Four-state Non-malleable 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}
}

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