Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Non-malleable code, Split-state, Explicit Constructions, Expanders

Original Publication (in the same form): ArXiV

Date: received 28 Sep 2018, last revised 20 Mar 2019

Contact author: pmrrasmussen at icloud com

Available format(s): PDF | BibTeX Citation

Note: Resubmitted with revised introduction and acknowledgement.

Version: 20190320:101159 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]