Abstract
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. 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 α ∈ [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{\Omega}(n^{1/7}))\). Alternatively, it is possible to improve the error to \(\exp(-\tilde{\Omega}(n))\) at the cost of making the construction Monte Carlo with success probability \(1-\exp(-\Omega(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.
A draft of the full version of this paper appears in [6].
Chapter PDF
Similar content being viewed by others
Keywords
References
Aggarwal, D., Dodis, Y., Lovett, S.: Non-malleable codes from additive combinatorics. ECCC Technical Report TR13-081 (2013)
Barak, B., Rao, A., Shaltiel, R., Wigderson, A.: 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. Annals of Mathematics 176(3), 1483–1544 (2012)
Bourgain, J.: More on the Sum-Product phenomenon in prime fields and its applications. International Journal of Number Theory 1(1), 1–32 (2005)
Cheraghchi, M.: Applications of Derandomization Theory in Coding. PhD thesis, Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland (2010), http://eccc.hpi-web.de/static/books/Applications_of_Derandomization_Theory_in_Coding/
Cheraghchi, M., Guruswami, V.: Capacity of non-malleable codes. ECCC Technical Report TR13-118 (2013)
Cheraghchi, M., Guruswami, V.: Explicit optimal rate non-malleable codes for bit-tampering. IACR Technical Report 2013/565 (2013), http://eprint.iacr.org/2013/565
Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing 2(17), 230–261 (1988)
Cramer, R., Dodis, Y., Fehr, S., Padró, C., Wichs, D.: Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 471–488. Springer, Heidelberg (2008)
Dodis, Y., Li, X., Wooley, T.D., Zuckerman, D.: Privacy amplification and non-malleable extractors via character sums. In: Proceedings of FOCS 2011, pp. 668–677 (2011)
Dodis, Y., Wichs, D.: Non-malleable extractors and symmetric key cryptography from weak secrets. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 601–610 (2009)
Dziembowski, S., Kazana, T., Obremski, M.: Non-malleable codes from two-source extractors. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 239–257. Springer, Heidelberg (2013)
Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes. In: Proceedings of Innovations in Computer Science, ICS 2010 (2010)
Forney, G.D.: Concatenated Codes. MIT Press (1966)
Gohen, G., Raz, R., Segev, G.: Non-malleable extractors with short seeds and applications to privacy amplification. In: Proceedings of CCC 2012, pp. 298–308 (2012)
Guruswami, V., Smith, A.: Codes for computationally simple channels: Explicit constructions with optimal rate. In: Proceedings of FOCS 2010, pp. 723–732 (2010)
Justesen, J.: A class of constructive asymptotically good algebraic codes. IEEE Transactions on Information Theory 18, 652–656 (1972)
Kalai, Y., Li, X., Rao, A.: 2-source extractors under computational assumptions and cryptography with defective randomness. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 617–626 (2009)
Kaplan, E., Naor, M., Reingold, O.: Derandomized constructions of k-wise (almost) independent permutations. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX and RANDOM 2005. LNCS, vol. 3624, pp. 354–365. Springer, Heidelberg (2005)
Li, X.: Non-malleable extractors, two-source extractors and privacy amplification. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 688–697 (2012)
Rao, A.: A 2-source almost-extractor for linear entropy. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol. 5171, pp. 549–556. Springer, Heidelberg (2008)
Raz, R.: Extractors with weak random seeds. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 11–20 (2005)
Raz, R., Yehudayoff, A.: Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. Journal of Computer and System Sciences 77(1), 167–190 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 International Association for Cryptologic Research
About this paper
Cite this paper
Cheraghchi, M., Guruswami, V. (2014). Non-malleable Coding against Bit-Wise and Split-State Tampering. In: Lindell, Y. (eds) Theory of Cryptography. TCC 2014. Lecture Notes in Computer Science, vol 8349. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54242-8_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-54242-8_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54241-1
Online ISBN: 978-3-642-54242-8
eBook Packages: Computer ScienceComputer Science (R0)