@inproceedings{aggarwal2022rate,
author = {Aggarwal, Divesh and Sekar, Sruthi and Kanukurthi, Bhavana and Obremski, Maciej and Obbattu, Sai Lakshmi Bhavana},
title = {Rate One-Third Non-malleable Codes},
booktitle = {STOC 2022},
year = {2022},
month = {June},
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 10−6! In this work, we build a Non-malleable Code with rate 1/3. This nearly matches the rate 1/2 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.},
url = {http://approjects.co.za/?big=en-us/research/publication/rate-one-third-non-malleable-codes/},
}