(Nondeterministic) Hardness vs. Non-malleability

. 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 untam-perable CRS [Cheraghchi, Guruswami ITCS’14; Faust, Mukherjee, Ven-turi, 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 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