Expander graphs are non-malleable codes

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

1 Citation (Scopus)
32 Downloads (Pure)

Abstract

Any d-regular graph on n vertices with spectral expansion ? satisfying n = ?(d3 log(d)/?) yields a O (?3d/2 ) -non-malleable code for single-bit messages in the split-state model.

Original languageEnglish
Title of host publication1st Conference on Information-Theoretic Cryptography, ITC 2020
EditorsYael Tauman Kalai, Adam D. Smith, Daniel Wichs
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2020
Pages1-10
Article number6
ISBN (Electronic)9783959771511
DOIs
Publication statusPublished - 2020
Event1st Conference on Information-Theoretic Cryptography, ITC 2020 - Virtual, Boston, United States
Duration: 17 Jun 202019 Jun 2020

Conference

Conference1st Conference on Information-Theoretic Cryptography, ITC 2020
Country/TerritoryUnited States
CityVirtual, Boston
Period17/06/202019/06/2020
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume163
ISSN1868-8969

Bibliographical note

Publisher Copyright:
© Peter Michael Reichstein Rasmussen and Amit Sahai; licensed under Creative Commons License CC-BY

Keywords

  • Expander Graph
  • Mixing Lemma
  • Non-Malleable Code

Cite this