Mukul Kulkarni: on-Malleable Codes from Average-Case Hardness: AC0, Decision Trees, and Streaming Space-Bounded Tampering
Friday, February 23, 2018 - 10:30am to 12:00pm
Location:
Hewlett, G882
Speaker:
Mukul Kulkarni, University of Maryland, College Park
Seminar group:
Abstract:
We show a general framework for constructing non-malleable codes against tampering families with average-case hardness bounds. Our framework adapts ideas from the Naor-Yung double encryption paradigm such that to protect against tampering in a class F, it suffices to have average-case hard distributions for the class, and underlying primitives (encryption and non-interactive, simulatable proof systems) satisfying certain properties with respect to the class.
We instantiate our scheme in a variety of contexts, yielding efficient, non-malleable codes (NMC) against the following tampering classes:
(1) Computational NMC against AC0 tampering, in the CRS model, assuming a PKE scheme with decryption in AC0 and NIZK.
(2) Computational NMC against bounded-depth decision trees (of depth t^\eps, where t is the number of input variables and 0<\eps <1), in the CRS model and under the same computational assumptions as above.
(3) Information theoretic NMC (with no CRS) against a streaming, space-bounded adversary, namely an adversary modeled as a read-once branching program with bounded width.
Ours are the first constructions that achieve each of the above in an efficient way, under the standard notion of non-malleability.
We instantiate our scheme in a variety of contexts, yielding efficient, non-malleable codes (NMC) against the following tampering classes:
(1) Computational NMC against AC0 tampering, in the CRS model, assuming a PKE scheme with decryption in AC0 and NIZK.
(2) Computational NMC against bounded-depth decision trees (of depth t^\eps, where t is the number of input variables and 0<\eps <1), in the CRS model and under the same computational assumptions as above.
(3) Information theoretic NMC (with no CRS) against a streaming, space-bounded adversary, namely an adversary modeled as a read-once branching program with bounded width.
Ours are the first constructions that achieve each of the above in an efficient way, under the standard notion of non-malleability.
This is a joint work with my advisor Dana Dachman-Soled; and with Marshall Ball, and Tal Malkin from Columbia University