(Nondeterministic) Hardness vs. Non-malleability

Marshall Ball, Dana Dachman-Soled, Julian Loss

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


We present the first truly explicit constructions of non-malleable codes against tampering by bounded polynomial size circuits. These objects imply unproven circuit lower bounds and our construction is secure provided E requires exponential size nondeterministic circuits, an assumption from the derandomization literature. Prior works on NMC for polysize circuits, either required an untamperable CRS [Cheraghchi, Guruswami ITCS’14; Faust, Mukherjee, Venturi, Wichs EUROCRYPT’14] or very strong cryptographic assumptions [Ball, Dachman-Soled, Kulkarni, Lin, Malkin EUROCRYPT’18; Dachman-Soled, Komargodski, Pass CRYPTO’21]. Both of works in the latter category only achieve non-malleability with respect to efficient distinguishers and, more importantly, utilize cryptographic objects for which no provably secure instantiations are known outside the random oracle model. In this sense, none of the prior yields fully explicit codes from non-heuristic assumptions. Our assumption is not known to imply the existence of one-way functions, which suggests that cryptography is unnecessary for non-malleability against this class. Technically, security is shown by non-deterministically reducing polynomial size tampering to split-state tampering. The technique is general enough that it allows us to construct the first seedless non-malleable extractors [Cheraghchi, Guruswami TCC’14] for sources sampled by polynomial size circuits [Trevisan, Vadhan FOCS’00] (resp. recognized by polynomial size circuits [Shaltiel CC’11]) and tampered by polynomial size circuits. Our construction is secure assuming E requires exponential size Σ4 -circuits (resp. Σ3 -circuits), this assumption is the state-of-the-art for extracting randomness from such sources (without non-malleability). Several additional results are included in the full version of this paper [Eprint 2022/070]. First, we observe that non-malleable codes and non-malleable secret sharing [Goyal, Kumar STOC’18] are essentially equivalent with respect to polynomial size tampering. In more detail, assuming E is hard for exponential size nondeterministic circuits, any efficient secret sharing scheme can be made non-malleable against polynomial size circuit tampering. Second, we observe that the fact that our constructions only achieve inverse polynomial (statistical) security is inherent. Extending a result from [Applebaum, Artemenko, Shaltiel, Yang CC’16] we show it is impossible to do better using black-box reductions. However, we extend the notion of relative error from [Applebaum, Artemenko, Shaltiel, Yang CC’16] to non-malleable extractors and show that they can be constructed from similar assumptions. Third, we observe that relative-error non-malleable extractors can be utilized to render a broad class of cryptographic primitives tamper and leakage resilient, while preserving negligible security guarantees.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings
EditorsYevgeniy Dodis, Thomas Shrimpton
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages30
ISBN (Print)9783031158018
StatePublished - 2022
Event42nd Annual International Cryptology Conference, CRYPTO 2022 - Santa Barbara, United States
Duration: Aug 15 2022Aug 18 2022

Publication series

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


Conference42nd Annual International Cryptology Conference, CRYPTO 2022
Country/TerritoryUnited States
CitySanta Barbara

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of '(Nondeterministic) Hardness vs. Non-malleability'. Together they form a unique fingerprint.

Cite this