Efficient non-malleable codes and key derivations against poly size tampering circuits

A talk by Pratyay Mukherjee about a joint work with Sebastian Faust, Daniele Venturi and Daniel Wichs

Pratyay's talk was in two parts, the first part being about the construction of non-malleable codes and the second on an application of these codes.

Part 1: A non-malleable code (NMC) is a code which consists of two randomized methods, encoding and decoding. It has the property that if a codeword is tampered with then the decoding algorithm will either reconstruct the message that was encoded or output a completely unrelated message. This is an interesting primitive which finds applications in tamper resilient cryptography.

However, since there is no secret key nothing prevents an adversary from doing a man-in-the-middle attack by decoding a codeword, flip a bit, and then reencode the modified message. This obviously makes it seem impossible to succeeded in constructing a NMC for unrestricted tampering functions, but Pratyay and his co authors overcome this impossibility result by only considering a restricted class of functions. In particular they are able to show that for any fixed polynomial p there exist an efficient NMC for any family of functions which can be computed by a circuit with size less than 2^p=P, assuming a common reference string (CRS).

More specifically by fixing P they give a specific construction for a family of efficient codes, parameterized by a CRS, which are non-malleable with high probability. The construction consists of two encodings: an inner encoding and an outer encoding. The outer encoding uses a t-wise independent hash function h. More specifically let C_i be the encoding that is output by the inner encoding, then the outer encoding is C_o=C_i || h (C_i). For the inner encoding they use a leakage resilient code, specifically Partyay uses the code with the encoding function computing c_i= r || h'(r) xor s for any r and input s where h' is again some limited independent hash function.

For the second part of the talk Pratyay introduced a new primitive called non-malleable key-derivation function and also proposed a efficient construction that is secure against poly sized circuits. In fact their construction is information theoretically secure and achieves optimal rate. A usage of this primitive is for example to construct a tamper resilient stream cipher.