"Locally Testable Non-Malleable Codes"
Sourya Roy (UC Riverside)
Monday, February 24, 2020, 2:00pm
EBU3B, Room 4258
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.
This is a joint work with Silas Richelson.