Paper 2021/1042

Simplicity Meets Near-Optimal Rate: Non-malleable Codes and Non-malleable Two-source Extractors via Rate Boosters

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

Abstract

At ITCS 2010, Dziembowski, Pietrzak and Wichs introduced Non-malleable Codes (NMCs). Non-malleability is one of the strongest and most challenging notions of security considered in cryptography and protects against tampering attacks. In the context of coding schemes, non-malleability requires that it be infeasible to tamper the codeword of a message into the codeword of a related message. A natural and 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. Cheraghchi and Guruswami (ITCS 2014) showed that one cannot obtain NMCs in the 2-split state model with rate better than 1/2. Since its inception, this area has witnessed huge strides leading to the construction of a constant-rate NMC in the 2-split state model due to Aggarwal and Obremski (FOCS 2020). However, the rate of this construction -- roughly 1/1,500,000 -- is nowhere close to the best achievable rate of 1/2! In this work, we dramatically improve this status quo by building a rate booster that converts any augmented non-malleable code into an augmented non-malleable code with a rate of 1/3. Using similar, but simpler techniques we also obtain rate boosters that convert any unbalanced (with sources of unequal length) non-malleable 2-source extractor into an unbalanced non-malleable 2-source extractor with rate 1/2. The beauty of our construction lies in its simplicity. In particular, if we apply our rate booster to the non-malleable code construction by Aggarwal, Dodis and Lovett (STOC 2014), then all we need is one instance of the inner-product extractor, one instance of a seeded extractor, and an affine-evasive function for the construction to work.