Paper 2015/1253

Non-Malleable Functions and Their Applications

Yu Chen and Baodong Qin and Jiang Zhang and Yi Deng and Sherman S. M. Chow

Abstract

We formally study ``non-malleable functions'' (NMFs), a general cryptographic primitive which simplifies and relaxes ``non-malleable one-way/hash functions'' (NMOWHFs) introduced by Boldyreva et al. (ASIACRYPT 2009) and refined by Baecher et al. (CT-RSA 2010). NMFs focus on deterministic functions, rather than probabilistic one-way/hash functions considered in the literature of NMOWHFs. We mainly follow Baecher et al. to formalize a game-based definition. Roughly, a function $f$ is non-malleable if given an image $y^* \leftarrow f(x^*)$ for a randomly chosen $x^*$, it is hard to output a mauled image $y$ with a $\phi$ from some transformation class s.t. $y = f(\phi(x^*))$. A distinctive strengthening of our non-malleable notion is that $\phi(x^*) = x^*$ is always allowed. We also consider adaptive non-malleability, which stipulates that non-malleability holds even when an inversion oracle is available. We investigate the relations between non-malleability and one-wayness in depth. In the non-adaptive setting, we show that for any achievable transformation class, non-malleability implies one-wayness for poly-to-one functions but not vise versa. In the adaptive setting, we show that for most algebra-induced transformation class, adaptive non-malleability (ANM) is equivalent to adaptive one-wayness (AOW) for injective functions. These two results establish interesting theoretical connections between non-malleability and one-wayness for functions, which extend to trapdoor functions as well, and thus resolve some open problems left by Kiltz et al. (EUROCRYPT 2010). Notably, the implication AOW $\Rightarrow$ ANM not only yields constructions of NMFs from adaptive trapdoor functions, which partially solves an open problem posed by Boldyreva et al.(ASIACRYPT 2009), but also provides key conceptual insight into addressing non-trivial copy attacks in the context of related-key attacks (RKA). Finally, we show that NMFs lead to a simple black-box construction of continuous non-malleable key derivation functions recently proposed by Qin et al. (PKC 2015), which have proven to be very useful in achieving RKA-security for numerous cryptographic primitives.