Cryptology ePrint Archive: Report 2021/1042

Rate One-Third Non-malleable Codes

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

Category / Keywords: foundations / Non-malleable Codes, Extractors, Information theoretic Cryptography, non-malleable commitments

Date: received 11 Aug 2021, last revised 18 Aug 2021

Contact author: dcsdiva at nus edu sg, bhavana at iisc ac in, oslbhavana at gmail com, obremski math at gmail com, sruthi sekar1 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210818:160603 (All versions of this report)

Short URL: ia.cr/2021/1042


[ Cryptology ePrint archive ]