IACR News item: 27 May 2013
Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett
ePrint ReportPrior 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 [DPW10], or (2) relied on advanced cryptographic assumptions (such as non-interactive zero-knowledge proofs and leakage-resilient encryption) [LL12], or (3) could only encode 1-bit messages [DKO13]. 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 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 (,) 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 Quasi-polynomial Freiman-Ruzsa Theorem} (which was recently established by Sanders [San12] as a step towards resolving the Polynomial Freiman-Ruzsa conjecture [Gre05]).
Additional news items may be found on the IACR news page.