Expander graphs are non-malleable codes

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


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
Article number6
ISBN (Electronic)9783959771511
Publication statusPublished - 2020
Event1st Conference on Information-Theoretic Cryptography, ITC 2020 - Virtual, Boston, United States
Duration: 17 Jun 202019 Jun 2020


Conference1st Conference on Information-Theoretic Cryptography, ITC 2020
LandUnited States
ByVirtual, Boston
SeriesLeibniz International Proceedings in Informatics, LIPIcs

Bibliographical note

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

    Research areas

  • Expander Graph, Mixing Lemma, Non-Malleable Code

Number of downloads are based on statistics from Google Scholar and www.ku.dk

No data available

ID: 271818850