2013/09/04 by Mahdi Cheraghchi, Venkatesan Guruswami, Cheraghchi, Mahdi +1 · 1 citation
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1309.1151
openalex publication_date 2013/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Dziembowski et al. show existence of non-malleable codes for any class of tampering functions of bounded size. We consider constructions of coding schemes against two well-studied classes of tampering functions: bit-wise tampering functions (where the adversary tampers each bit of the encoding independently) and split-state adversaries (where two independent adversaries arbitrarily tamper each half of the encoded sequence). 1. For bit-tampering, we obtain explicit and efficiently encodable and decodable codes of length n achieving rate 1-o(1) and error (security) exp(-Ω(n1/7)). We improve the error to exp(-Ω(n)) at the cost of making the construction Monte Carlo with success probability 1-exp(-Ω(n)). Previously, the best known construction of bit-tampering codes was the Monte Carlo construction of Dziembowski et al. (ICS 2010) achieving rate ~.1887. 2. We initiate the study of seedless non-malleable extractors as a variation of non-malleable extractors introduced by Dodis and Wichs (STOC 2009). We show that construction of non-malleable codes for the split-state model reduces to construction of non-malleable two-source extractors. We prove existence of such extractors, which implies that codes obtained from our reduction can achieve rates arbitrarily close to 1/5 and exponentially small error. Currently, the best known explicit construction of split-state coding schemes is due to Aggarwal, Dodis and Lovett (ECCC TR13-081) which only achieves vanishing (polynomially small) rate.