Skip to main content
Open Access Publications from the University of California

UC San Diego

UC San Diego Previously Published Works bannerUC San Diego

Non-malleable codes from additive combinatorics

Published Web Location
No data is associated with this publication.

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” F is completely unrestricted, they are known to exist for many broad tampering families 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 L, R over the vector space Fpn (for a prime p and large enough dimension n): if L and R are uniformly random over Fpn, and f, g : Fpn → Fpn are two arbitrary functions on L and R, then the joint distribution (L, R, f(L), g(R)) is “close” to the convex combination of “affine distributions” ((U, aU + b) | a, b ∈ Fp), where U is uniformly random in Fp. 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].

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item