STOC Conference 2022 Conference Paper
Rate one-third non-malleable codes
- Divesh Aggarwal
- Bhavana Kanukurthi
- Sai Lakshmi Bhavana Obbattu
- Maciej Obremski
- Sruthi Sekar
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.