Non-malleable Coding Against Bit-Wise and Split-State Tampering. Cheraghchi, M. & Guruswami, V. In Proceedings of Theory of Cryptography Conference (TCC), pages 440–464, 2014. Extended version in Journal of Cryptology.
Non-malleable Coding Against Bit-Wise and Split-State Tampering [link]Link  Non-malleable Coding Against Bit-Wise and Split-State Tampering [link]Paper  doi  abstract   bibtex   
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^{α 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(-Ω̃(n^{1/7}))$. Alternatively, it is possible to improve the error to $\exp(-Ω̃(n))$ at the cost of making the construction Monte Carlo with success probability $1-\exp(-Ω(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.
@INPROCEEDINGS{ref:conf:CG14b,
  author =	 {Mahdi Cheraghchi and Venkatesan Guruswami},
  title =	 {Non-malleable Coding Against Bit-Wise and
                  Split-State Tampering},
  year =	 2014,
  booktitle =	 "Proceedings of Theory of Cryptography Conference
                  {(TCC)}",
  pages =	 "440--464",
  doi =		 {10.1007/978-3-642-54242-8_19},
  keywords =	 {Information theory, Tamper-resilient cryptography,
                  Coding theory, Error detection, Randomness
                  extractors},
  url_Link =
                  {https://link.springer.com/chapter/10.1007/978-3-642-54242-8_19},
  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 $\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{\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 \textit{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.  },
  note =	 {Extended version in {Journal of Cryptology.}},
  url_Paper =	 {https://eccc.weizmann.ac.il//report/2013/121}
}

Downloads: 0