TY - GEN
T1 - A rate-optimizing compiler for non-malleable codes against bit-wise tampering and permutations
AU - Agrawal, Shashank
AU - Gupta, Divya
AU - Maji, Hemanta K.
AU - Pandey, Omkant
AU - Prabhakaran, Manoj
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2015.
PY - 2015
Y1 - 2015
N2 - A non-malleable code protects messages against a class of tampering functions. Informally, a code is non-malleable if the effect of applying any tampering function on an encoded message is to either retain the message or to replace it with an unrelated message. Two main challenges in this area – apart from establishing the feasibility against different families of tampering – are to obtain explicit constructions and to obtain high-rates for such constructions. In this work, we present a compiler to transform low-rate (in fact, zero rate) non-malleable codes against certain class of tampering into an optimal-rate – i.e., rate 1 – non-malleable codes against the same class. If the original code is explicit, so is the new one. When applied to the family of bit-wise tampering functions, this subsumes (and greatly simplifies) a recent result of Cheraghchi and Guruswami (TCC 2014). Further, our compiler can be applied to nonmalleable codes against the class of bit-wise tampering and bit-level permutations. Combined with the rate-0 construction in a companion work, this yields the first explicit rate-1 non-malleable code for this family of tampering functions. Our compiler uses a new technique for boot-strapping non-malleability by introducing errors, that may be of independent interest.
AB - A non-malleable code protects messages against a class of tampering functions. Informally, a code is non-malleable if the effect of applying any tampering function on an encoded message is to either retain the message or to replace it with an unrelated message. Two main challenges in this area – apart from establishing the feasibility against different families of tampering – are to obtain explicit constructions and to obtain high-rates for such constructions. In this work, we present a compiler to transform low-rate (in fact, zero rate) non-malleable codes against certain class of tampering into an optimal-rate – i.e., rate 1 – non-malleable codes against the same class. If the original code is explicit, so is the new one. When applied to the family of bit-wise tampering functions, this subsumes (and greatly simplifies) a recent result of Cheraghchi and Guruswami (TCC 2014). Further, our compiler can be applied to nonmalleable codes against the class of bit-wise tampering and bit-level permutations. Combined with the rate-0 construction in a companion work, this yields the first explicit rate-1 non-malleable code for this family of tampering functions. Our compiler uses a new technique for boot-strapping non-malleability by introducing errors, that may be of independent interest.
KW - Explicit construction
KW - Information theoretic
KW - Non-malleable codes
KW - Rate 1
KW - Rate-optimizing compiler
UR - http://www.scopus.com/inward/record.url?scp=84924709344&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84924709344&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-46494-6_16
DO - 10.1007/978-3-662-46494-6_16
M3 - Conference contribution
AN - SCOPUS:84924709344
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 375
EP - 397
BT - Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Proceedings
A2 - Dodis, Yevgeniy
A2 - Nielsen, Jesper Buus
PB - Springer
T2 - 12th Theory of Cryptography Conference, TCC 2015
Y2 - 23 March 2015 through 25 March 2015
ER -