CISPA
Browse

(Nondeterministic) Hardness vs. Non-Malleability

Download (731.11 kB)
conference contribution
posted on 2023-11-29, 18:21 authored by Marshall Ball, Dana Dachman-Soled, Julian LossJulian Loss
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 con- struction 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, Gu- ruswami ITCS’14; Faust, Mukherjee, Venturi, Wichs EUROCRYPT’14] or very strong cryptographic assumptions [Ball, Dachman-Soled, Kulkarni, Lin, Malkin EUROCRYPT’18; Dachman-Soled, Komar- godski, 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 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). We additionally 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. Unfortunately, all of our constructions only achieve inverse polynomial (statistical) security. 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. We additionally 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.

History

Preferred Citation

Marshall Ball, Dana Dachman-Soled and Julian Loss. (Nondeterministic) Hardness vs. Non-Malleability. In: Advances in Cryptology (CRYPTO). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

Advances in Cryptology (CRYPTO)

Legacy Posted Date

2022-06-29

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3717, title = "(Nondeterministic) Hardness vs. Non-Malleability", author = "Ball, Marshall and Dachman-Soled, Dana and Loss, Julian", booktitle="{Advances in Cryptology (CRYPTO)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC