Revisiting the Sanders-Freiman-Ruzsa Theorem in and its Application to Non-malleable Codes

D Aggarwal, J Briët - arXiv preprint arXiv:1602.02788, 2016 - arxiv.org
arXiv preprint arXiv:1602.02788, 2016arxiv.org
Non-malleable codes (NMCs) protect sensitive data against degrees of corruption that
prohibit error detection, ensuring instead that a corrupted codeword decodes correctly or to
something that bears little relation to the original message. The split-state model, in which
codewords consist of two blocks, considers adversaries who tamper with either block
arbitrarily but independently of the other. The simplest construction in this model, due to
Aggarwal, Dodis, and Lovett (STOC'14), was shown to give NMCs sending k-bit messages …
Non-malleable codes (NMCs) protect sensitive data against degrees of corruption that prohibit error detection, ensuring instead that a corrupted codeword decodes correctly or to something that bears little relation to the original message. The split-state model, in which codewords consist of two blocks, considers adversaries who tamper with either block arbitrarily but independently of the other. The simplest construction in this model, due to Aggarwal, Dodis, and Lovett (STOC'14), was shown to give NMCs sending k-bit messages to -bit codewords. It is conjectured, however, that the construction allows linear-length codewords. Towards resolving this conjecture, we show that the construction allows for code-length . This is achieved by analysing a special case of Sanders's Bogolyubov-Ruzsa theorem for general Abelian groups. Closely following the excellent exposition of this result for the group by Lovett, we expose its dependence on for the group , where is a prime.
arxiv.org