Expander Graphs are Non-Malleable Codes

Abstract

Any $d$-regular graph on $n$ vertices with spectral expansion $\lambda$ satisfying $n=\Omega (d^3\log (d)/\lambda )$ yields a $O\left(\frac{{\lambda }^{3/2}}{d}\right)$-non-malleable code for single-bit messages in the split-state model.

10 pages Resubmitted with revised introduction and acknowledgement