Expander Graphs are Non-Malleable Codes

Peter M.  R.  Rasmussen; Amit Sahai

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 code Split-state Explicit Constructions Expanders
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: 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},
      url = {https://eprint.iacr.org/2018/929}
}