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

BibTeX

@misc{cryptoeprint:2018/929,
      author = {Peter M.  R.  Rasmussen and Amit Sahai},
      title = {Expander Graphs are Non-Malleable Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2018/929},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/929}},
      url = {https://eprint.iacr.org/2018/929}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.