Capacity of non-malleable codes
Mahdi Cheraghchi, Venkatesan Guruswami · 2014
Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages s in a manner so that tampering the codeword causes the decoder to either output s or a message that is independent of s. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family F of tampering functions that is not too large (for instance, when lF| ≤ 22αn for some α < 1 where n is the number of bits in a codeword).