Four-state Non-malleable Codes with Explicit Constant Rate

Title : Four-state Non-malleable Codes with Explicit Constant Rate

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 de ned 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 2 F. Nearly all known constructions of NMCs are for 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 = 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 ecient non-malleable code in the t-splitstate model, for t = 4, that achieves a constant rate of 1 3+ , for any constant  > 0, and error 2???? (`=logc+1`), where ` is the length of the message and c > 0 is a constant.

Conference Details : Fifteenth IACR Theory of Cryptography Conference - TCC 2017

Date :12/11/2017 ,

Venue : Baltimore USA

Published At :Fifteenth IACR Theory of Cryptography Conference - TCC 2017,

View :

Style Switcher

Predefined Colors

Layout Style

Header Color

Footer Top Color

Footer Bottom Color