Non-malleable codes for small-depth circuits

Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li Yang Tan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e. AC 0 tampering functions), our codes have codeword length n = k 1+o(1 ) for a k-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay and Li (STOC 2017), which had codeword length 2 O(√k) . Our construction remains efficient for circuit depths as large as Θ(log(n)/loglog(n)) (indeed, our codeword length remains n < k 1+ϵ ), and extending our result beyond this would require separating P from NC 1 . We obtain our codes via a new efficient non-malleable reduction from small-depth tampering to split-state tampering. A novel aspect of our work is the incorporation of techniques from unconditional derandomization into the framework of non-malleable reductions. In particular, a key ingredient in our analysis is a recent pseudorandom switching lemma of Trevisan and Xue (CCC 2013), a derandomization of the influential switching lemma from circuit complexity; the randomness-efficiency of this switching lemma translates into the rate-efficiency of our codes via our non-malleable reduction.

Original languageEnglish (US)
Title of host publicationProceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
EditorsMikkel Thorup
PublisherIEEE Computer Society
Pages826-837
Number of pages12
ISBN (Electronic)9781538642306
DOIs
StatePublished - Nov 30 2018
Event59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France
Duration: Oct 7 2018Oct 9 2018

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2018-October
ISSN (Print)0272-5428

Other

Other59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
Country/TerritoryFrance
CityParis
Period10/7/1810/9/18

Keywords

  • Non-malleable codes
  • Small-depth circuits
  • Switching lemma

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Non-malleable codes for small-depth circuits'. Together they form a unique fingerprint.

Cite this