Expander Graphs are Non-Malleable Codes
arXiv:1810.00106v25 citations
Originality Incremental advance
AI Analysis
This provides a new construction for non-malleable codes, addressing security in tamper-resistant cryptography, though it is incremental as it builds on known graph-based methods.
The paper tackles the problem of constructing non-malleable codes for single-bit messages in the split-state model by showing that expander graphs with specific spectral expansion properties yield such codes with an error bound of O(λ^{3/2}/d).
Any $d$-regular graph on $n$ vertices with spectral expansion $λ$ satisfying $n = Ω(d^3\log(d)/λ)$ yields a $O\left(\frac{λ^{3/2}}{d}\right)$-non-malleable code for single-bit messages in the split-state model.