"Non-Malleable Codes from Additive Combinatorics"
Shachar Lovett
UCSD
Monday, April 22, 2013, 2:00 pm
EBU3B, Room 4140
Abstract:
Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker (or the channel) can completely overwrite the encoded message. Informally, a code is non-malleable 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'' is completely unrestricted, they are known to exist for some broad families of tampering functions.
One such natural family is the family of tampering functions in the so called split-state 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 individually. The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes, motivating the question of designing efficient non-malleable codes in this model. Prior to this work, non-malleable codes in the split-state model received considerable attention in the literature, but were either (1) constructed in the random oracle model, or (2) relied on advanced cryptographic assumptions (such as non-interactive zero-knowledge proofs and leakage-resilient encryption), or (3) could only encode 1-bit messages. As our main result, we build the first efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model.
The heart of our constructions relies on the following new property of the inner product function. Let L,R be chosen uniformly in a vector field Fn. Let f,g:Fn -> Fn be arbitrary functions. Then the joint distribution of <L,R>,<f(L),g(R)> in F2 is close (in statistical distance) to a convex combination of affine functions (U,aU+b) where U is uniform in F. The proof of this fact relies on recent results in additive combinatorics.
Joint work with Divesh Aggarwal (NYU) and Yevgeniy Dodis (NYU). Paper link http://eprint.iacr.org/2013/201.