You are looking at a specific version 20190320:101159 of this paper. See the latest version.

Paper 2018/929

Expander Graphs are Non-Malleable Codes

Peter M. R. Rasmussen and Amit Sahai

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.

Note: Resubmitted with revised introduction and acknowledgement.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. ArXiV
Keywords
Non-malleable codeSplit-stateExplicit ConstructionsExpanders
Contact author(s)
pmrrasmussen @ icloud com
History
2019-03-20: revised
2018-10-02: received
See all versions
Short URL
https://ia.cr/2018/929
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.