Non-malleable codes against bounded polynomial time tampering

Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Huijia Lin, Tal Malkin

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

Abstract

We construct efficient non-malleable codes (NMC) that are (computationally) secure against tampering by functions computable in any fixed polynomial time. Our construction is in the plain (no-CRS) model and requires the assumptions that (1) E is hard for NP circuits of some exponential 2 βn (β> 0) size (widely used in the derandomization literature), (2) sub-exponential trapdoor permutations exist, and (3) P -certificates with sub-exponential soundness exist. While it is impossible to construct NMC secure against arbitrary polynomial-time tampering (Dziembowski, Pietrzak, Wichs, ICS ’10), the existence of NMC secure against O(nc) -time tampering functions (for any fixed c), was shown (Cheraghchi and Guruswami, ITCS ’14) via a probabilistic construction. An explicit construction was given (Faust, Mukherjee, Venturi, Wichs, Eurocrypt ’14) assuming an untamperable CRS with length longer than the runtime of the tampering function. In this work, we show that under computational assumptions, we can bypass these limitations. Specifically, under the assumptions listed above, we obtain non-malleable codes in the plain model against O(nc) -time tampering functions (for any fixed c), with codeword length independent of the tampering time bound. Our new construction of NMC draws a connection with non-interactive non-malleable commitments. In fact, we show that in the NMC setting, it suffices to have a much weaker notion called quasi non-malleable commitments—these are non-interactive, non-malleable commitments in the plain model, in which the adversary runs in O(nc) -time, whereas the honest parties may run in longer (polynomial) time. We then construct a 4-tag quasi non-malleable commitment from any sub-exponential OWF and the assumption that E is hard for some exponential size NP -circuits, and use tag amplification techniques to support an exponential number of tags.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsYuval Ishai, Vincent Rijmen
PublisherSpringer Verlag
Pages501-530
Number of pages30
ISBN (Print)9783030176525
DOIs
StatePublished - 2019
Event38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019 - Darmstadt, Germany
Duration: May 19 2019May 23 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11476 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019
Country/TerritoryGermany
CityDarmstadt
Period5/19/195/23/19

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Non-malleable codes against bounded polynomial time tampering'. Together they form a unique fingerprint.

Cite this