Document Open Access Logo

Expander Graphs Are Non-Malleable Codes

Authors Peter Michael Reichstein Rasmussen, Amit Sahai

PDF
Thumbnail PDF

File

LIPIcs.ITC.2020.6.pdf
  • Filesize: 456 kB
  • 10 pages

Document Identifiers

Author Details

Peter Michael Reichstein Rasmussen
  • Basic Algorithms Research Copenhagen, University of Copenhagen, Denmark
Amit Sahai
  • UCLA, Los Angeles, CA, USA

Funding

  • Rasmussen, Peter Michael Reichstein: Supported in part by grant 16582, Basic Algorithms Research Copenhagen (BARC), from the VILLUM Foundation.
  • Sahai, Amit: Supported in part from a DARPA/ARL SAFEWARE award, NSF Frontier Award 1413955, and NSF grant 1619348, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, an equipment grant rom Intel, and an Okawa Foundation Research Grant. This material is based upon work supported by the Defense Advanced Research Projects Agency through the ARL under Contract W911NF-15-C- 0205. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, or the U.S. Government.

Acknowledgements

A significant effort was made to simplify our proof as much as possible, which eventually resulted in the approximately 2-page proof of our main result presented here; we thank Anders Aamand and Jakob Bæk Tejs Knudsen for suggestions and insights regarding the main theorem that helped simplify and improve the results presented. Furthermore, we thank Aayush Jain, Yuval Ishai, and Dakshita Khurana for early discussions regarding simple constructions of split-state non-malleable codes not based on expander graphs.

Cite AsGet BibTex

Peter Michael Reichstein Rasmussen and Amit Sahai. Expander Graphs Are Non-Malleable Codes. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITC.2020.6

Abstract

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

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic primitives
  • Mathematics of computing → Spectra of graphs
Keywords
  • Non-Malleable Code
  • Expander Graph
  • Mixing Lemma

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Divesh Aggarwal, Yevgeniy Dodis, and Shachar Lovett. Non-malleable codes from additive combinatorics. In Symposium on Theory of Computing, STOC, 2014. Google Scholar
  2. Eshan Chattopadhyay, Vipul Goyal, and Xin Li. Non-malleable extractors and codes, with their many tampered extensions. In Symposium on Theory of Computing, STOC, 2016. Google Scholar
  3. Eshan Chattopadhyay and David Zuckerman. Non-malleable codes against constant split-state tampering. In Foundations of Computer Science, FOCS, 2014. Google Scholar
  4. Stefan Dziembowski, Tomasz Kazana, and Maciej Obremski. Non-malleable codes from two-source extractors. In CRYPTO, 2013. Google Scholar
  5. Stefan Dziembowski, Krzysztof Pietrzak, and Daniel Wichs. Non-malleable codes. In ICS, 2010. Google Scholar
  6. Xin Li. Improved non-malleable extractors, non-malleable codes and independent source extractors. In Symposium on Theory of Computing, STOC, 2017. Google Scholar
  7. Luca Trevisan. Luca trevisan’s `in theory' blog. https://lucatrevisan.wordpress.com/2011/02/28/cs359g-lecture-16-constructions-of-expanders/. Accessed: 2018-09-27. URL: https://lucatrevisan.wordpress.com/2011/02/28/cs359g-lecture-16-constructions-of-expanders/.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact