Rate One-Third Non-malleable Codes

Divesh Aggarwal; Sruthi Sekar; Bhavana Kanukurthi; Maciej Obremski; Sai Lakshmi Bhavana Obbattu

Paper 2021/1042

Rate One-Third Non-malleable Codes

Divesh Aggarwal, Sruthi Sekar, Bhavana Kanukurthi, Maciej Obremski, and Sai Lakshmi Bhavana Obbattu

Abstract

At ITCS 2010, Dziembowski, Pietrzak, and Wichs introduced Non-malleable Codes (NMCs) which protect against tampering of a codeword of a given message into the codeword of a related message. A well-studied model of tampering is the $2$ -split-state model where the codeword consists of two independently tamperable states. As with standard error-correcting codes, it is of great importance to build codes with high rates. Following a long line of work, Aggarwal and Obremski (FOCS 2020) showed the first constant rate non-malleable code in the $2 -$ split state model; however this constant was a minuscule ! In this work, we build a Non-malleable Code with rate . This nearly matches the rate lower bound for this model due to Cheraghchi and Guruswami (ITCS 2014). Our construction is simple, requiring just an inner-product extractor, a seeded extractor, and an affine-evasive function.

Note: The author ordering is randomized here.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. STOC 2022
Keywords: Non-malleable Codes Extractors Information theoretic Cryptography non-malleable commitments
Contact author(s): dcsdiva @ nus edu sg
bhavana @ iisc ac in
oslbhavana @ gmail com
obremski math @ gmail com
sruthi sekar1 @ gmail com
History: 2022-03-04: last of 2 revisions; 2021-08-16: received; See all versions
Short URL: https://ia.cr/2021/1042
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1042,
      author = {Divesh Aggarwal and Sruthi Sekar and Bhavana Kanukurthi and Maciej Obremski and Sai Lakshmi Bhavana Obbattu},
      title = {Rate One-Third Non-malleable Codes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1042},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1042}
}