Four-State Non-malleable Codes with Explicit Constant Rate
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:
- PDF / 760,711 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 78 Downloads / 185 Views
Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India [email protected], [email protected] 2 Department of Mathematics, Indian Institute of Science, Bangalore, India [email protected] 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 ∈ 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 efficient non-malleable code in the t1 , for any split-state model, for t = 4, that achieves a constant rate of 3+ζ constant ζ > 0, and error 2−Ω(/log message and c > 0 is a constant.
1
c+1
)
, where is the length of the
Introduction
Error correcting codes allow for the correction of errors introduced in data. However, their applicability is limited by the fact that they can only correct a bounded number of errors. When data is completely overwritten, no protection can be guaranteed. Non-malleable codes, introduced in the work of Dziembowski et al. [15], guarantee that, errors caused to the data will render it either independent of the underlying message or leave it unchanged. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 344–375, 2017. https://doi.org/10.1007/978-3-319-70503-3_11
Four-State Non-malleable Codes with Explicit Constant Rate
345
Non-malleable codes are parameterized by a family of tampering functions, F, and they guarantee non-malleability only when m∗ = Dec(f (Enc(m))) where f ∈ F and Enc, Dec are the encode and decode functions respectively. (In other words, there is no guarantee when f ∈ / F.) Informally, given a tampering family F, a non-malleable code (Enc, Dec) encodes a given message m into a codeword c ← Enc(m) s.t. if c is modified to c˜ = f (c) by some f ∈ F, then the message m ˜ = Dec(˜ c) contained i
Data Loading...
