Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-117 | 23rd June 2020 03:13

Locally Testable Non-Malleable Codes

RSS-Feed




Revision #1
Authors: Silas Richelson, Sourya Roy
Accepted on: 23rd June 2020 03:13
Downloads: 509
Keywords: 


Abstract:

In this work we adapt the notion of non-malleability for codes of Dziembowski, Pietrzak
and Wichs (ICS 2010) to locally testable codes. Roughly speaking, a locally testable code is
non-malleable if any tampered codeword which passes the local test with good probability is
close to a valid codeword which either encodes the original, or an unrelated message.
We instantiate our definition by proving that a Reed-Muller-type code is non-malleable in
the following sense: any adversary who independently tampers the coordinates of the code
so that the tampered code passes the test with good probability, is tampering the underlying
polynomial according to an affine transformation.
To the best of our knowledge, prior to this work, polynomial codes were not known to
possess any non-malleability guarantees. Our analysis builds on the sampler-based decoding
techniques common to several recent works.
As an additional contribution, we describe a new (standard) non-malleable code against
affine tampering which is much simpler than prior constructions, and achieves better parameters. Finally, we prove a composition theorem for locally testable non-malleable codes which
allows for obtaining codes via concatenation.


Paper:

TR19-117 | 4th September 2019 01:41

Locally Testable Non-Malleable Codes





TR19-117
Authors: Silas Richelson, Sourya Roy
Publication: 10th September 2019 15:26
Downloads: 841
Keywords: 


Abstract:

In this work we adapt the notion of non-malleability for codes or Dziembowski, Pietrzak and Wichs (ICS 2010) to locally testable codes. Roughly speaking, a locally testable code is non-malleable if any tampered codeword which passes the local test with good probability is close to a valid codeword which either encodes the original, or an unrelated message.
We instantiate our definition by proving that a Reed-Muller-type code is non-malleable in the following sense: any adversary who independently tampers the coordinates of the code so that the tampered code passes the test with good probability, is tampering the underlying polynomial according to an affine transformation.
To the best of our knowledge, prior to this work, polynomial codes were not known to possess any non-malleability guarantees. Our analysis builds on the sampler-based decoding techniques common to several recent works.



ISSN 1433-8092 | Imprint