Paper 2017/930

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 fF. Nearly all known constructions of NMCs are for the -split-state family, where the adversary tampers each of the 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 with being the codeword length and, in (ITCS 2014), show an upper bound of on the best achievable rate for any split state NMC. For , 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 , 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 -split-state model, for , that achieves a constant rate of , for any constant , and error , where is the length of the message and is a constant.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in TCC 2017
Keywords
information theoretic cryptographynon-malleability
Contact author(s)
bhavana @ iisc ac in
oslbhavana @ gmail com
sruthi sekar1 @ gmail com
History
2017-09-25: received
Short URL
https://ia.cr/2017/930
License
Creative Commons Attribution
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},
      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.