Capacity of non-malleable codes
File(s)
Accepted version
Accepted version
Author(s)
Cheraghchi, M
Guruswami, V
Type
Journal Article
Abstract
Non-malleable codes, introduced by Dziembowski et al., encode messages s in a manner, so that tampering the codeword causes the decoder to either output s or a message that is independent of s. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family P of tampering functions that is not too large (for instance, when I≤I 22αn for some α <; 1, where n is the number of bits in a codeword). In this paper, we study the capacity of non-malleable codes, and establish optimal bounds on the achievable rate as a function of the family size, answering an open problem from Dziembowski et al. Specifically, We prove that for every family P with IFI I≤I 22αn, there exist non-malleable codes against P with rate arbitrarily close to 1-α [this is achieved with high probability (w.h.p.) by a randomized construction]. We show the existence of families of size exp(nO(1)2αn) against which there is no non-malleable code of rate 1 - α (in fact this is the case w.h.p for a random family of this size). We also show that 1 - α is the best achievable rate for the family of functions, which are only allowed to tamper the first αn bits of the codeword, which is of special interest. As a corollary, this implies that the capacity of non-malleable coding in the split-state model (where the tampering function acts independently but arbitrarily on the two halves of the codeword, a model which has received some attention recently) equals 1/2. We also give an efficient Monte Carlo construction of codes of rate close to 1 with polynomial time encoding and decoding that is non-malleable against any fixed c > 0 and family P of size 2nc, in particular tampering functions with, say, cubic size circuits.
Date Issued
2016-03-01
Date Acceptance
2015-10-22
Citation
IEEE Transactions on Information Theory, 2016, 62 (3), pp.1097-1118
ISSN
1557-9654
Publisher
IEEE
Start Page
1097
End Page
1118
Journal / Book Title
IEEE Transactions on Information Theory
Volume
62
Issue
3
Replaces
10044/1/33731
Copyright Statement
© 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Subjects
Science & Technology
Technology
Computer Science, Information Systems
Engineering, Electrical & Electronic
Computer Science
Engineering
Cryptography
cryptographic protocols
codes
privacy
data security
Networking & Telecommunications
0801 Artificial Intelligence and Image Processing
0906 Electrical and Electronic Engineering
1005 Communications Technologies
Publication Status
Published
Date Publish Online
2015-12-24