Imperial College London
Portrait Picture

Dr Mahdi Cheraghchi

Faculty of Engineering, Department of Computing

Honorary Senior Lecturer
 
 
 
//

Contact

 

m.cheraghchi Website CV

 
 
//

Location

 

353ACE ExtensionSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Cheraghchi:2017:10.1007/s00145-015-9219-z,
author = {Cheraghchi, M and Guruswami, V},
doi = {10.1007/s00145-015-9219-z},
journal = {Journal of Cryptology},
pages = {191--241},
title = {Non-malleable coding against bit-wise and split-state tampering},
url = {http://dx.doi.org/10.1007/s00145-015-9219-z},
volume = {30},
year = {2017}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - 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 22α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(−Ω (n1/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-m
AU  - Cheraghchi,M
AU  - Guruswami,V
DO  - 10.1007/s00145-015-9219-z
EP  - 241
PY  - 2017///
SN  - 0933-2790
SP  - 191
TI  - Non-malleable coding against bit-wise and split-state tampering
T2  - Journal of Cryptology
UR  - http://dx.doi.org/10.1007/s00145-015-9219-z
UR  - http://hdl.handle.net/10044/1/63224
VL  - 30
ER  -
Download