Tamper Detection and Continuous Non-Malleable Codes.
Zahra Jafargholi, Daniel Wichs · 2014
We consider a public and keyless code (Enc,Dec) which is used to encode a message m and derive a codeword c = Enc(m). The codeword can be adversarially tampered via a function f ∈ F from some “tampering function family ” F, resulting in a tampered value c ′ = f(c). We study the different types of security guarantees that can be achieved in this scenario for different families F of tampering attacks. Firstly, we initiate the general study of tamper-detection codes, which must detect that tampering occurred and output Dec(c′) = ⊥. We show that such codes exist for any family of functions F over n bit codewords, as long as |F | < 22n is sufficiently smaller than the set of all possible functions, and the functions f ∈ F are further restricted in two ways: (1) they can only have a few fixed points x such that f(x) = x, (2) they must have high entropy of f(x) over a random x. Such codes can also be made efficient when |F | = 2poly(n). For example, F can be the family of all low-degree polynomials excluding constant and identity polynomials. Such tamper-detection codes generalize the algebraic manipulation detection (AMD) codes of Cramer et al. (EUROCRYPT ’08). Next, we revisit non-malleable codes, which were introduced by Dziembowski, Pietrzak and Wichs (ICS ’10) and require that Dec(c′) either decodes to the original message m, or to some unrelated value (possibly ⊥) that doesn’t provide any information about m. We give a modular construction of non-malleable codes by