Non-Malleable Codes Against Bounded Polynomial Time Tampering.
Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Huijia Lin, Tal Malkin · IACR Cryptology ePrint Archive · 2018
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) \(\mathbf {E}\) is hard for \(\mathbf {NP}\) circuits of some exponential \(2^{\beta n}\) (\(\beta >0\)) size (widely used in the derandomization literature), (2) sub-exponential trapdoor permutations exist, and (3) \(\mathbf {P}\)-certificates with sub-exponential soundness exist.