ECCC-Report TR21-117https://eccc.weizmann.ac.il/report/2021/117Comments and Revisions published for TR21-117en-usFri, 04 Mar 2022 07:55:04 +0200
Revision 3
| Rate One-Third Non-malleable Codes |
Divesh Aggarwal,
Sruthi Sekar,
Bhavana Kanukurthi,
Maciej Obremski,
SaiLakshmiBhavana Obbattu
https://eccc.weizmann.ac.il/report/2021/117#revision3At 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. Fri, 04 Mar 2022 07:55:04 +0200https://eccc.weizmann.ac.il/report/2021/117#revision3
Revision 2
| Rate One-Third Non-malleable Codes |
Divesh Aggarwal,
Bhavana Kanukurthi,
SaiLakshmiBhavana Obbattu,
Maciej Obremski,
Sruthi Sekar
https://eccc.weizmann.ac.il/report/2021/117#revision2At 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.Fri, 20 Aug 2021 20:31:23 +0300https://eccc.weizmann.ac.il/report/2021/117#revision2
Revision 1
| Simplicity Meets Near-Optimal Rate: Non-malleable Codes and Non-malleable Two-source Extractors via Rate Boosters |
Divesh Aggarwal,
Bhavana Kanukurthi,
SaiLakshmiBhavana Obbattu,
Maciej Obremski,
Sruthi Sekar
https://eccc.weizmann.ac.il/report/2021/117#revision1At 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.
Mon, 16 Aug 2021 14:02:13 +0300https://eccc.weizmann.ac.il/report/2021/117#revision1
Paper TR21-117
| Simplicity Meets Near-Optimal Rate: Non-malleable Codes and Non-malleable Two-source Extractors via Rate Boosters |
Divesh Aggarwal,
Bhavana Kanukurthi,
SaiLakshmiBhavana Obbattu,
Maciej Obremski,
Sruthi Sekar
https://eccc.weizmann.ac.il/report/2021/117At 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.Fri, 13 Aug 2021 16:49:56 +0300https://eccc.weizmann.ac.il/report/2021/117