Expander Graphs are Non-Malleable Codes

Peter M.  R.  Rasmussen; Amit Sahai

Paper 2018/929 Original: eprint.iacr.org/2018/929 ↗

Expander Graphs are Non-Malleable Codes

Peter M. R. Rasmussen

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
History: 2019-03-20: last updated; 2018-10-02: published
Short URL: https://ia.cr/2018/929
License: https://creativecommons.org/licenses/by/4.0/

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}
}