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 in the split-state model.

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

Date: received 28 Sep 2018

Contact author: pmrrasmussen at icloud com

Available format(s): PDF | BibTeX Citation

Version: 20181002:040542 (All versions of this report)

Short URL: ia.cr/2018/929


[ Cryptology ePrint archive ]