Paper 2013/201
Nonmalleable Codes from Additive Combinatorics
Divesh Aggarwal, Yevgeniy Dodis, and Shachar Lovett
Abstract
Nonmalleable codes provide a useful and meaningful security guarantee in situations where traditional errorcorrection (and even errordetection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is nonmalleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. Although such codes do not exist if the family of "tampering functions" \cF is completely unrestricted, they are known to exist for many broad tampering families \cF. One such natural family is the family of tampering functions in the so called {\em splitstate} model. Here the message m is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with L and R {\em individually}. The splitstate tampering arises in many realistic applications, such as the design of nonmalleable secret sharing schemes, motivating the question of designing efficient nonmalleable codes in this model. Prior to this work, nonmalleable codes in the splitstate model received considerable attention in the literature, but were either (1) constructed in the random oracle model [DPW10], or (2) relied on advanced cryptographic assumptions (such as noninteractive zeroknowledge proofs and leakageresilient encryption) [LL12], or (3) could only encode 1bit messages [DKO13]. As our main result, we build the first efficient, multibit, informationtheoreticallysecure nonmalleable code in the splitstate model. The heart of our construction uses the following new property of the innerproduct function <L,R> over the vector space F_p^n (for any prime p and large enough dimension n): if L and R are uniformly random over F_p^n, and f,g: F_p^n \rightarrow F_p^n are two arbitrary functions on L and R, the joint distribution (<L,R>,<f(L),g(R)>) is ``close'' to the convex combination of "affine distributions" {(U,c U+d) c,d \in F_p}, where U is uniformly random in F_p. In turn, the proof of this surprising property of the inner product function critically relies on some results from additive combinatorics, including the so called {\em Quasipolynomial FreimanRuzsa Theorem} (which was recently established by Sanders [San12] as a step towards resolving the Polynomial FreimanRuzsa conjecture [Gre05]).
Metadata
 Available format(s)
 Category
 Applications
 Publication info
 Published elsewhere. Unknown status
 Keywords
 Non malleable codesCombinatorics
 Contact author(s)
 divesha @ cs nyu edu
 History
 20171206: last of 4 revisions
 20130409: received
 See all versions
 Short URL
 https://ia.cr/2013/201
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/201, author = {Divesh Aggarwal and Yevgeniy Dodis and Shachar Lovett}, title = {Nonmalleable Codes from Additive Combinatorics}, howpublished = {Cryptology {ePrint} Archive, Paper 2013/201}, year = {2013}, url = {https://eprint.iacr.org/2013/201} }