CROSSING Research Seminar

Organizer: Jacqueline Brendel, CROSSING

Abstract

Non-malleable codes (Dziembowski, Pietrzak and Wichs, ICS 2010) are a relaxed version of error-correcting and error-detecting codes where it's possible to decode to a valid but independent message. Their main application concerns protecting arbitrary cryptographic primitives against related-key attacks (RKAs). Even when using codes guaranteed to be non-malleable against a single tampering attempt, one obtains RKA security against poly-many tampering attacks at the price of assuming perfect memory erasures. In contrast, continuously non-malleable codes (Faust, Mukherjee, Nielsen, and Venturi, TCC 2014) do not suffer from this limitation, as the non-malleability guarantee holds against poly-many tampering attempts. Unfortunately, there are only a handful of constructions of continuously non-malleable codes, while standard non-malleable codes are known for a large variety of tampering families. We change this state of affairs by providing the first constructions of continuously non-malleable codes in the following natural settings:

- Against decision-tree tampering, where, in each tampering attempt, every bit of the tampered codeword can be set arbitrarily after adaptively reading a fraction of bits within the input codeword. Notably, this class includes NC0.

- Against bounded polynomial-depth tampering, where in each tampering attempt the adversary can select any tampering function that can be computed by a circuit of bounded polynomial depth (and unbounded polynomial size).

Speaker Bio

Elena is a Ph.D. student in the Chair of Applied Cryptography at TU Darmstadt under the supervision of Sebastian Faust. Her main area of interest is provable security in the presence of leakage and tampering.