A new security proof for FMNV continuous non-malleable encoding scheme

A non-malleable code is a variant of an encoding scheme which is resilient to tampering attacks. The main idea behind nonmalleable coding is that the adversary should not be able to obtain any valuable information about the message. Non-malleable codes are used in tamper-resilient cryptography and protecting memories against tampering attacks. Many different types of nonmalleability have already been formalized and defined in current literature, among which continuous non-malleability is the setup in which the messages are protected against adversaries who may issue polynomially many tampering queries. The first continuous non-malleable encoding scheme has been proposed by Faust et. al. (FMNV) in 2014. In this article, we propose a new proof of continuous non-malleability of the FMNV scheme, while the new proof will also give rise to an improved and more efficient version of this scheme. The new proof also shows that one may achieve continuous nonmalleability of the same security by using a leakage resilient storage scheme with (about (k 1)(log(q) − 2)) fewer bits for the leakage bound (where k is the output size of the collision resistant hash function and q is the maximum number of tampering queries). This shows that the new scheme is more efficient and practical for tamper resilient applications.