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.

Title, author ordering according to a random generator, minor updations to introduction section of the paper.

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.

abstract and title

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 a 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.

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 a 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.

Further, as an application of our $1/3$-rate augmented NMC (which we also prove to be leakage resilient), we give an extremely simple computational binding and statistical hiding non-malleable commitment scheme using only standard assumptions, and with a communication cost of $41$ times the length of the message to be committed, which is optimal up to a constant factor.