Four-State Non-malleable Codes with Explicit Constant Rate

Autor: Sruthi Sekar, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu
Rok vydání: 2019
Předmět:
Zdroj: Journal of Cryptology. 33:1044-1079
ISSN: 1432-1378
0933-2790
Popis: 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}$$ 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}$$. 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)$$ 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^{-\varOmega (\ell / log^{c+1} \ell )}$$, where $$\ell $$ is the length of the message and $$c > 0$$ is a constant.
Databáze: OpenAIRE
Externí odkaz: