Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR21-117 | 20th August 2021 20:31

Rate One-Third Non-malleable Codes

RSS-Feed




Revision #2
Authors: Divesh Aggarwal, Bhavana Kanukurthi, SaiLakshmiBhavana Obbattu, Maciej Obremski, Sruthi Sekar
Accepted on: 20th August 2021 20:31
Downloads: 47
Keywords: 


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.



Changes to previous version:

abstract and title


Revision #1 to TR21-117 | 16th August 2021 14:02

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





Revision #1
Authors: Divesh Aggarwal, Bhavana Kanukurthi, SaiLakshmiBhavana Obbattu, Maciej Obremski, Sruthi Sekar
Accepted on: 16th August 2021 14:02
Downloads: 56
Keywords: 


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


Paper:

TR21-117 | 11th August 2021 20:56

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


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



ISSN 1433-8092 | Imprint