Welcome to the resource topic for 2021/1042
Title:
Rate One-Third Non-malleable Codes
Authors: Divesh Aggarwal, Sruthi Sekar, Bhavana Kanukurthi, Maciej Obremski, 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 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.
ePrint: https://eprint.iacr.org/2021/1042
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .