Non-Malleable Codes from Additive Combinatorics

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 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” ${\mathcal F}$ is completely unrestricted, they are known to exist for many broad tampering families ${\mathcal F}$. 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 either (1) were constructed in the random oracle model, or (2) relied on advanced cryptographic assumptions (such as noninteractive 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 construction uses the following new property of the inner-product function $\langle{L,R\rangle}$ over the vector space ${{F}_p}^n$ (for a prime $p$ and large enough dimension $n$): if $L$ and $R$ are uniformly random over ${\mathbb{F}_p}^n$, and $f,g:{\mathbb{F}_p}^n\rightarrow {\mathbb{F}_p}^n$ are two arbitrary functions on $L$ and $R$, then the joint distribution $(\langle{L,R\rangle},\langle{f(L),g(R)\rangle})$ is “close” to the convex combination of “affine distributions” $\{(U,aU+b)\mid a,b\in \mathbb{F}_p\}$, where $U$ is uniformly random in ${\mathbb{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 quasi-polynomial Freiman--Ruzsa theorem, which was recently established by Sanders [Anal. PDE, 5 (2012), pp. 627--655] as a step toward resolving the polynomial Freiman--Ruzsa conjecture [B. Green, in Surveys in Combinatorics, London Mathematical Society, London, 2005, pp. 1--29].