Non-malleable Coding Against Bit-Wise and Split-State Tampering

详细信息    查看全文

• 作者：Mahdi Cheraghchi ; Venkatesan Guruswami
• 关键词：Information theory ; Tamper ; resilient cryptography ; Coding theory ; Error detection ; Randomness extractors
• 刊名：Journal of Cryptology
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：30
• 期：1
• 页码：191-241
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Coding and Information Theory; Computational Mathematics and Numerical Analysis; Combinatorics; Probability Theory and Stochastic Processes; Communications Engineering, Networks;
• 出版者：Springer US
• ISSN：1432-1378
• 卷排序：30

文摘

Non-malleable coding, introduced by Dziembowski et al. (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. Non-malleable coding is possible against any class of adversaries of bounded size. In particular, Dziembowski et al. show that such codes exist and may achieve positive rates for any class of tampering functions of size at most \(2^{2^{\alpha n}}\), for any constant \(\alpha \in [0, 1)\). However, this result is existential and has thus attracted a great deal of subsequent research on explicit constructions of non-malleable codes against natural classes of adversaries. In this work, we consider constructions of coding schemes against two well-studied classes of tampering functions; namely, bit-wise tampering functions (where the adversary tampers each bit of the encoding independently) and the much more general class of split-state adversaries (where two independent adversaries arbitrarily tamper each half of the encoded sequence). We obtain the following results for these models. (1) For bit-tampering adversaries, we obtain explicit and efficiently encodable and decodable non-malleable codes of length n achieving rate \(1-o(1)\) and error (also known as “exact security”) \(\exp (-\tilde{\varOmega }(n^{1/7}))\). Alternatively, it is possible to improve the error to \(\exp (-\tilde{\varOmega }(n))\) at the cost of making the construction Monte Carlo with success probability \(1-\exp (-\varOmega (n))\) (while still allowing a compact description of the code). Previously, the best known construction of bit-tampering coding schemes was due to Dziembowski et al. (ICS 2010), which is a Monte Carlo construction achieving rate close to .1887. (2) We initiate the study of seedless non-malleable extractors as a natural variation of the notion 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 a general result on existence of seedless non-malleable extractors, which implies that codes obtained from our reduction can achieve rates arbitrarily close to 1 / 5 and exponentially small error. In a separate recent work, the authors show that the optimal rate in this model is 1 / 2. 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.